LeetCode-in-All
32. Longest Valid Parentheses
Hard
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.
Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.
Example 3:
Input: s = “”
Output: 0
Constraints:
0 <= s.length <= 3 * 104s[i]is'(', or')'.
Solution
func longestValidParentheses(s string) int {
max := 0
left, right := 0, 0
n := len(s)
for i := 0; i < n; i++ {
ch := s[i]
if ch == '(' {
left++
} else {
right++
}
if right > left {
left, right = 0, 0
}
if left == right {
max = maxInt(max, left+right)
}
}
left, right = 0, 0
for i := n - 1; i >= 0; i-- {
ch := s[i]
if ch == '(' {
left++
} else {
right++
}
if left > right {
left, right = 0, 0
}
if left == right {
max = maxInt(max, left+right)
}
}
return max
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}