Problem Statement (
link):
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
Analysis:
Stack should be the first thought when we are asked about parentheses validation problem, as we could push the '(' and match it with any ')' we meet in the future.
However, the stack algorithm for this problem is not straight-forward. The reason is simple, as the problem allows any kind of parentheses combination; while the conventional stack algorithm requires consecutive validness.
Let's not abandon the conventional stack idea, i.e.,
push when meet '(',
pop when meet ')'. Additionally, suppose we use a
start variable to record the index of the latest possible start of a valid sequence:
- First, after a sequential
push() operation, if the stack is empty, it implies so far we only see ')'. Thus we need to keep updating
start variable to indicate the start of possible valid sequence shouldn't include any previous ')'s;
- Next, if we meet some ')' and
pop() them out, we want to keep updating
maxLen. However, there are two situations:
1) the stack is
empty after we
pop() something. For instance,
s = " ( ) ", after we
pop() the
')', the stack should be empty and we need to update the
maxLen. If we have
start indicating the possible start of a valid sequence,
start = -1 (which is also the initial value),
current valid length = i - start. And we update
maxLen by taking the
max between
current valid length and previous possible
maxLen.
2) the stack is not
empty after we
pop() something. For instance,
s = ' ( ( ) ', after we
pop the
')', the stack is not
empty, and we also need to update the
maxLen. Now,
current valid length = 2, which is actually
i - index of the first '(', the index of the first '(' could be obtained from peeking the top of the stack - as the stack is not empty right now, i.e.,
current valid length = i - stack.top(). Now, we get the idea that all the indices that are still in stack indicate the indices of the "invalid/unused" '('.
It's a bit difficult to get the idea of recording the valid length, working through an example would help.
Furthermore, the time complexity and worst space complexity is
O(n), where
n is length of the string.
Code:
class Solution {
public:
int longestValidParentheses(string s) {
int maxLen=0;
int start=-1; // the possible start of a valid seq
stack<int> st; // save the index of '('
for (int i=0; i<s.length(); i++) {
if (s[i]=='(') {
st.push(i);
}
else {
if (st.empty()) {
start=i;
}
else {
st.pop();
if (st.empty()) {
maxLen=max(maxLen, i-start);
}
else {
maxLen=max(maxLen, i-st.top());
}
}
}
}
return maxLen;
}
};
