# My O(n) solution using a stack

• ``````class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length(), longest = 0;
stack<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') st.push(i);
else {
if (!st.empty()) {
if (s[st.top()] == '(') st.pop();
else st.push(i);
}
else st.push(i);
}
}
if (st.empty()) longest = n;
else {
int a = n, b = 0;
while (!st.empty()) {
b = st.top(); st.pop();
longest = max(longest, a-b-1);
a = b;
}
longest = max(longest, a);
}
return longest;
}
};
``````

The workflow of the solution is as below.

1. Scan the string from beginning to end.
2. If current character is '(',
push its index to the stack. If current character is ')' and the
character at the index of the top of stack is '(', we just find a
matching pair so pop from the stack. Otherwise, we push the index of
')' to the stack.
3. After the scan is done, the stack will only
contain the indices of characters which cannot be matched. Then
let's use the opposite side - substring between adjacent indices
should be valid parentheses.
4. If the stack is empty, the whole input
string is valid. Otherwise, we can scan the stack to get longest
valid substring as described in step 3.

• This post is deleted!

• Your explanation is awsome !!

• Thanks! This is awesome!

• This is my DP solution, just one pass

V[i] represents number of valid parentheses matches from S[j to i] (j<i)

V[i] = V[i-1] + 2 + previous matches V[i- (V[i-1] + 2) ] if S[i] = ')' and '(' count > 0

``````public int longestValidParentheses(String s) {
char[] S = s.toCharArray();
int[] V = new int[S.length];
int open = 0;
int max = 0;
for (int i=0; i<S.length; i++) {
if (S[i] == '(') open++;
if (S[i] == ')' && open > 0) {
// matches found
V[i] = 2+ V[i-1];
if(i-V[i]>0)
V[i] += V[i-V[i]];
open--;
}
if (V[i] > max) max = V[i];
}
return max;
}``````

• Great solution. Only one small question: Do we need if(i-V[i]>0) ? I mean, i - V[i] should be always non negative and V[0] is always 0. Hence, do we need the if condition ?

• Consider the case "((()))". When i == 5, V[i] is 6. i - V[i] won't always be non-negative.

• "substring between adjacent indices should be valid parentheses." --- Great observations!

• That is the best one answer.

• awesome!!!!!!!!!!!!!!

• really smart!

• Thanks for your answer. In fact, we don't have to get the maximum length after the first scan. Instead, we can get it dynamically while push and pop, which makes the run time get better. Following is my code.

``````public class Solution {
public int longestValidParentheses(String s) {
int max = Integer.MIN_VALUE;
s += "x";
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ')' && !stack.empty() && s.charAt(stack.peek())== '(')
stack.pop();
else{
if(stack.empty()){
max = Math.max(max, i);
}
else
max = Math.max(max, i-stack.peek()-1);
stack.push(i);
}
}
return stack.empty() ? s.length() : max;
}
``````

}

• This is absolutely the best answer for this problem!

• This post is deleted!

``````int longestValidParentheses(string s) {
int size = s.size(), res = 0;
if(size < 2) return res;
stack<int> si;
for(int i = 0; i < size; ++i) {
if('(' == s[i]) si.push(i);
else {
if(si.empty()) si.push(i);
else {
if(s[si.top()] == '(') {
si.pop();
res = max(i - (si.empty()? -1: si.top()), res);
}
else si.push(i);
}
}
}
return res;
}
``````

• Great!!!!!!!

• good job!!!!.

• python version:

``````    def longestValidParentheses(self, s):
stack, res, s = [0], 0, ')'+s
for i in xrange(1, len(s)):
if s[i] == ')' and s[stack[-1]] == '(':
stack.pop()
res = max(res, i - stack[-1])
else:
stack.append(i)
return res``````

• Thanks for sharing,nice explanation.

• Upvoting cuz - you were practicing on the New Year's Eve too! :D

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.