Longest Valid Parentheses Problem
Description
LeetCode Problem 32.
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:
1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:
1
2
Input: s = ""
Output: 0
Constraints:
- 0 <= s.length <= 3 * 10^4
- s[i] is ‘(‘, or ‘)’.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1);
int ans = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
stk.push(i);
} else {
stk.pop();
if (stk.empty()) {
stk.push(i);
} else {
ans = max(ans, i - stk.top());
}
}
}
return ans;
}
};