This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #32 (Hard): Longest Valid Parentheses
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given a string containing just the characters
'('and')', find the length of the longest valid (well-formed) parentheses substring.
Examples:
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 * 10^4
- s[i] is '(', or ')'.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
One of the key things to realize about valid parentheses strings is that they're entirely self-satisfied, meaning that while you can have one substring that is entirely inside another, you can't have two substrings that only partially overlap.
This means that we can use a greedy O(N) time complexity solution to this problem without the need for any kind of backtracking. In fact, we should be able to use a very standard stack-based valid parentheses string algorithm with just three very minor modifications.
In a stadard valid parentheses string algorithm, we iterate through the string (S) and push the index (i) of any '(' to our stack. Whenever we find a ')', we match it with the last entry on the stack and pop said entry off. We know the string is not valid if we find a ')' while there are no '(' indexes in the stack with which to match it, and also if we have leftover '(' in the stack when we reach the end of S.
For this problem, we will need to add in a step that updates our answer (ans) when we close a parentheses pair. Since we stored the index of the '(' in our stack, we can easily find the difference between the ')' at i and the last entry in the stack, which should be the length of the valid substring which was just closed.
But here we run into a problem, because consecutive valid substrings can be grouped into a larger valid substring (ie, '()()' = 4). So instead of counting from the last stack entry, we should actually count from the second to last entry, to include any other valid closed substrings since the most recent '(' that will still remain after we pop the just-matched last stack entry off.
This, of course, brings us to the second and third changes. Since we're checking the second to last stack entry, what happens in the case of '()()' when you close the second valid substring yet there's only the one stack entry left at the time?
To avoid this issue, we can just wrap the entire string in another imaginary set of parentheses by starting with stack = [-1], indicating that there's an imaginary '(' just before the beginning of the string at i = 0.
The other issue is that we will want to continue even if the string up to i becomes invalid due to a ')' appearing when the stack is "empty", or in this case has only our imaginary index left. In that case, we can just effectively restart our stack by updating our imaginary '(' index (stack[0] = i) and continue on.
Then, once we reach the end of S, we can just return ans.
Implementation:
There are only minor differences in the code for all four languages.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var longestValidParentheses = function(S) {
let stack = [-1], ans = 0
for (let i = 0; i < S.length; i++)
if (S[i] === '(') stack.push(i)
else if (stack.length === 1) stack[0] = i
else stack.pop(), ans = Math.max(ans, i - stack[stack.length-1])
return ans
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def longestValidParentheses(self, S: str) -> int:
stack, ans = [-1], 0
for i in range(len(S)):
if S[i] == '(': stack.append(i)
elif len(stack) == 1: stack[0] = i
else:
stack.pop()
ans = max(ans, i - stack[-1])
return ans
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int longestValidParentheses(String S) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int ans = 0;
for (int i = 0; i < S.length(); i++)
if (S.charAt(i) == '(') stack.push(i);
else {
stack.pop();
if (stack.isEmpty()) stack.push(i);
else ans = Math.max(ans, i - stack.peek());
}
return ans;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int longestValidParentheses(string S) {
vector<int> stack = {-1};
int ans = 0;
for (int i = 0; i < S.size(); i++)
if (S[i] == '(') stack.push_back(i);
else if (stack.size() == 1) stack[0] = i;
else {
stack.pop_back();
ans = max(ans, i - stack.back());
}
return ans;
}
};
Top comments (4)
Can you elaborate what do you mean by this " you can't have two substrings that only partially overlap." ? Appreciate your help :)
Sure! If you find a valid parentheses substring in S, you cannot possibly find another one that starts inside, but ends outside, the first one. In order for that to be the case, you'd have to have an unmatched parenthesis in the first substring, which would make that substring not valid, by definition.
That makes a big difference, because it means we don't need to check every index as a starting point for a valid parentheses substring, which would be O(N^2) time. We can instead use a greedy approach in O(N) time.
Since valid substrings can fully contain other valid substrings, however, we need the help of a stack.
Hey there, just wanted to clarify what "longest valid" means. if
S = '())()()'would the longest be'()','()()', or'()()()'?Ah okay,
'()()'would be the answer, never mind!