# Concise one pass DP solution without stack

• left: remaining left parentheses that haven't been paired.
DP[i + 1]: longest paired parentheses ended at index i. (i from 0 to size - 1)

Once we met a ')' and have unpaired '(', increase the length by 2 based on the previous DP value. The trick is that the newly generated length may not be the final DP value.

For the following example : '(()())', note that DP index start from 1, not 0.

Suppose we just met the second ')', DP[5] = DP[4] + 2 = 0 + 2 = 2.
Now we should go back to the first ')' to check if there are previously matched string. If yes, add them up.
Thus, DP[5] += DP[5 - DP[5]]

``````class Solution {
public:
int longestValidParentheses(string s) {
int size = (int)s.size();
vector<int> DP(size + 1, 0);
int left = 0, longest = 0;
for(int i = 0; i < size; ++i){
if(s[i] == '('){
left++;
}else if(s[i] == ')' && left > 0){
DP[i + 1] = DP[i] + 2;
DP[i + 1] += DP[i + 1 - DP[i + 1]];
left--;
}
longest = max(longest, DP[i + 1]);
}
return longest;
}
};
``````

• Thanks for sharing your code!
I rewrote your code in C++ and it passed all the test cases. The issue is that I think there is no need for the DP array to be indexed from 1, so I simply start DP process from index 0 and everything seems right.
I think it is easier to understand your code by making the index of DP array equal to the S array, is there anything wrong with my code? Please feel free to give your comment, thanks in advance!

``````class Solution {
public:
int longestValidParentheses(string s)
{
vector<int> result(s.size(), 0);
int left = 0, maxLength = 0;

for(int i = 0; i != s.size(); i++)
{
if(s[i] == '(')
left++;
else if(left)
{
left--;
result[i] = result[i - 1] + 2;
result[i] += result[i - result[i]];
maxLength = max(maxLength, result[i]);
}
}
return maxLength;
}
};
``````

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