Algorithm Puzzles: Longest Valid Parentheses

Algorithm Puzzles everyday every week sometimes: Longest Substring Without Repeating Characters

Puzzle

Puzzle from leetcode:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int longestValidParentheses(const std::string& s) {
std::stack<int> stack;
int res = 0;

stack.push(-1);

for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
res = std::max(res, i - stack.top());
}
}
}
return res;
}
};