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
impl Solution {
pub fn longest_valid_parentheses(s: String) -> i32 {
let mut max_len = 0;
let mut left = 0;
let mut right = 0;
let n = s.len();
let chars: Vec<char> = s.chars().collect();
// Left to right pass
for i in 0..n {
if chars[i] == '(' {
left += 1;
} else {
right += 1;
}
if right > left {
left = 0;
right = 0;
}
if left == right {
max_len = max_len.max(left + right);
}
}
// Right to left pass
left = 0;
right = 0;
for i in (0..n).rev() {
if chars[i] == '(' {
left += 1;
} else {
right += 1;
}
if left > right {
left = 0;
right = 0;
}
if left == right {
max_len = max_len.max(left + right);
}
}
max_len as i32
}
}