# My DP, O(n) solution without using stack

• My solution uses DP. The main idea is as follows: I construct a array longest[], for any longest[i], it stores the longest length of valid parentheses which is end at i.

And the DP idea is :

If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.

Else if s[i] is ')'

If s[i-1] is '(', longest[i] = longest[i-2] + 2

Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]

For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.

``````   int longestValidParentheses(string s) {
if(s.length() <= 1) return 0;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')'){
if(s[i-1] == '('){
longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;
curMax = max(longest[i],curMax);
}
else{ // if s[i-1] == ')', combine the previous length.
if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
curMax = max(longest[i],curMax);
}
}
}
//else if s[i] == '(', skip it, because longest[i] must be 0
}
return curMax;
}
``````

Updated: thanks to Philip0116, I have a more concise solution(though this is not as readable as the above one, but concise):

``````int longestValidParentheses(string s) {
if(s.length() <= 1) return 0;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')' && i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
curMax = max(longest[i],curMax);
}
}
return curMax;
}``````

• It seems the formular longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2] is not correct. Consider input "())())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6. But actually longest[5] is 0.

• Please see the condition in the code: if ( i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '(' ), i-longest[i-1]-1 = 5 - longest[4] -1 = 5 -2 -1 = 2, and s[2] = ')', which is not equal to '('. So the formula will not be executed. longest[5] will remain as 0.

• My java solution with both stack and an array....It is very easy to understand. Maybe it is the only good part compared to the other space-saving solution.

``````public class Solution {
public int longestValidParentheses(String s){
if (s==null||s.length()==0) return 0;

Stack<Integer> stack= new Stack<Integer>();	//Store indices of '('
int[] result=new int[s.length()];//Store the length of the current longest valid sequence.
Arrays.fill(result, 0);

int max=0;

for (int i=0;i<s.length();i++)
if (s.charAt(i)=='(')
stack.push(i);

else if (s.charAt(i)==')'){
if (stack.isEmpty())
continue;
else if (stack.peek()>0)
result[i]=2+result[stack.pop()-1]+result[i-1];//May connect two valid sequences, or increase the length of current valid sequence.
else {
result[i]=2+result[i-1];//Handle the special case that the leftmost char is a '('
stack.pop();
}

max=Math.max(result[i],max);
}
return max;
}
}``````

• I like your solution! And I think it is no need to consider the condition "s[i-1] == '('" since "s[i-longest[i-1]-1] == '('" actually concludes this case. We could just use "if (i-1>=0 && i-longest[i-1]-1 >=0 && s[i-longest[i-1]-1] == '(')"

• philip you are right

• Yes. You are right, Philip, thank you. Didn't notice that. The solution is based on my thought, never realize that I could optimize it.

• I had the same idea, except a bit different handling the current being `)` and previous also being `)` case. My Python code below:

``````def longestValidParentheses(self, s):
dp = [0]
left = right = 0
last = None
for paren in s:
if paren == '(':
left += 1
dp.append(0)
else:
right += 1
if right > left:
dp.append(0)
right = left = 0
continue

if last == '(':
dp.append(dp[-2] + 1)
else:
n = dp[-1] + 1
# look back, for cases like ()(())
n += dp[-2 * n]
dp.append(n)
last = paren

return 2 * max(dp)``````

• Nice solutions! Very easy to understand. Philip0116's simplification is great!

• ``````class Solution {
public:
int longestValidParentheses(string s) {
s = ")" + s;
int n = s.length();
vector<int> longest(n,0);
int res = 0;
for (int i=1; i < n; i++) {
if (s[i]=='(')
longest[i] = 0;
else {
if (s[i-1]=='(') {
longest[i] = longest[i-2] + 2;
res = max(res, longest[i]);
} else {
if (s[i-longest[i-1]-1]=='(') {
longest[i] = longest[i-longest[i-1]-2] + longest[i-1] + 2;
res = max(res, longest[i]);
}
}
}

}

return res;
}
};
``````

i add a dummy ")". let the code easy to read.

• nice solution!!

• I tried to use the similar strategy but I got stuck where the 3rd else statement ....

• Thanks for your share. The following is edited from your solution. Just add a prefix.

``````int longestValidParentheses(string s) {
s = ")" + s;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')' && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2];
curMax = max(longest[i],curMax);
}
}
return curMax;
}
``````

python version:

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

• ``````class Solution
{
public:
int longestValidParentheses(string s)
{
int len = s.size(), maxLen = 0, validLeft = 0;
vector<int> iCount(len, 0);
for (int i = 0; i < len; ++i)
{
if ('(' == s[i]) ++validLeft;
else if (validLeft > 0)
{
--validLeft;
if ('(' == s[i - 1]) iCount[i] = iCount[i - 2] + 2;
else iCount[i] = iCount[i - 1] + 2 + iCount[i - 2 - iCount[i - 1]];
}
maxLen = iCount[i] > maxLen ? iCount[i] : maxLen;
}
return maxLen;
}
};``````

• JAVA version. Store the result to the last element of array. Make it one line shorter

``````public int longestValidParentheses(String s) {
s = ")" + s;
int[] longest = new int[s.length() + 1];

for (int i = 1; i < s.length(); i++){
if (s.charAt(i) == ')' && s.charAt(i - longest[i - 1] - 1) == '(') {
longest[i] = longest[i - 1] + 2 + longest[i - longest[i - 1] - 2];
longest[s.length()] = Math.max(longest[i], longest[s.length()]);
}
}

return longest[s.length()];
}``````

• Nice, personally, I believe the most natural solution for this problem is via DP.

• Here I have question that why longest[i] can be 0 when longest[j] > 0 where 0 < j < i? For example, for input '()((' , when i = 2, the string is '()(' which has a valid subset '()', making the longest[2] = 2, but why longest[2] = 0?

• My definition of longest[] array is "for any longest[i], it stores the longest length of valid parentheses which ENDs at i. " So when i = 2, and s[2] =='(', the longest VALID parentheses that ENDS at 2 is of length 0.

• what an excellent solution~!!

• Great solution, however, i got TLE when trying this.

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