```
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size(), longest = 0;
vector<int> dp(n + 1);
// there is valid parentheses when there are
// at least 2 character
for (int i = 2; i <= n; i++) {
// 1 1 3 2 3
// ( ) ( ( ) )
// ^ ^
// | |
// prev i
int prev = i - dp[i - 1] - 1;
// if current char is ')' and
// the first one before the last streak of valid parentheses is '('
// we add:
// 1. last streak before the new pair
// 2. the streak inside the new pair
// 3. the new pair
if (s[i - 1] == ')' && s[prev - 1] == '(') {
dp[i] = dp[prev - 1] + dp[i - 1] + 2;
longest = max(longest, dp[i]);
}
}
return longest;
}
};
```