Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
int longestValidParentheses(string s) {
int len_s = s.size();
int dp[len_s+1]{0};
int maxLen = 0;
for(int i = 1; i < len_s; i++){
if(s[i] == ')'){
if(s[i - 1] == '('){
dp[i] = (i-2>=0 ? dp[i - 2] : 0) + 2;
}
else{
if(i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(')
dp[i] = dp[i-1] + 2 + (i-dp[i-1]-2 >=0 ? dp[i - dp[i-1] - 2] : 0);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment