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
# @param {String} s
# @return {Integer}
def longest_valid_parentheses(s)
max = 0
left = 0
right = 0
n = s.length
ch = nil
(0...n).each do |i|
ch = s[i]
if ch == '('
left += 1
else
right += 1
end
if right > left
left = 0
right = 0
end
if left == right
max = [max, left + right].max
end
end
left = 0
right = 0
(n - 1).downto(0) do |i|
ch = s[i]
if ch == '('
left += 1
else
right += 1
end
if left > right
left = 0
right = 0
end
if left == right
max = [max, left + right].max
end
end
max
end