Longest Valid Parentheses

1. Problem Description

Given a string containing only ‘(’ and ‘)’, find the length of the longest valid (well-formed and consecutive) parentheses substring.

2. Approach

1. Approach 1
   • Validate parentheses with a stack + count the longest consecutive sequence

3. Implementation

3.1. Stack

func longestValidParentheses(s string) int {
    m := make(map[int]bool,0) 
    var stack []int
    for i, ch := range s {
        if ch == '(' {
            stack = append(stack, i)
        }else {
            if len(stack) > 0 {
                top := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                m[top] = true
                m[i] = true
            }
        }

    }
    maxCount := 0
    for index := range m {
        if m[index-1] {
            continue
        }
        count := 0
        for m[index] {
            count++
            index++
        }
        maxCount = max(maxCount, count)
    }
    return maxCount
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

4. References

• Longest Valid Parentheses - LeetCode