Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
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 * 104s[i] is '(', or ')'.Longest Valid Parentheses - LeetCode
The idea is go through the string and use DP to store the longest valid parentheses at that point.take example "()(())"i : [0,1,2,3,4,5]s : [( ,) ,( ,( ,) ,) ]DP:[0,2,0,0,2,6]
1, We count all the ‘(‘.2, If we find a ‘)’ and ‘(‘ counter is not 0, we have at least a valid result size of 2. “()"3, Check the the one before (i - 1). If DP[i - 1] is not 0 means we have something like this “(())” . This will have DP “0024"4, We might have something before "(())”. Take "()(())” example, Check the i = 1 because this might be a consecutive valid string.
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
vector<int> dp(n,0);
int leftcount = 0;
int res = 0;
for(int i=0;i<n;i++)
{
if(s[i]=='(')
leftcount++;
else if(leftcount>0)
{
dp[i] = dp[i-1] + 2;
dp[i] += i>=dp[i] ? dp[i-dp[i]] : 0;
res = max(res,dp[i]);
leftcount--;
}
}
return res;
}
};