Yay, we're back to solving "hard" leetcodes. I'm glad I still have some brain cells intact. Vibe coding -- I mean Agentic Engineering, aka Loop Engineering, aka Harness engineering (or whatever tf we decided to call it) -- hasn't fully fried them yet.
Ok so this problem wasn't too bad, especially if you're familiar with some of the similar problems (I think it was called ValidParentheses).
I drew some examples first to understand the answer for different types of inputs. Like before, you need to push each ( on the stack because it could receive a closed parentheses which would make it valid.
For any closed parentheses ) if the stack is not empty, that means there's at least one open parentheses, so you can pop it off.
But instead of just pushing a char onto the stack, I also pushed index because valid parentheses solutions can basically merge into each other. So I used a pair and a vector dp.
It starts as a vector the size of the input string, s, and each time we pop, we mark the indices with a 1 to show which indicies of the string are valid.
Then we loop over the vector and count the longest consecutive sequence of 1's.
I know this isn't the best solution because we loop over a container the size of n twice, when I think there's a way to do it once. But I'm too lazy to look at better answers. This is good enough for me.
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
stack<pair<char,int>> st;
vector<int> dp(n, 0);
for(int i = 0; i < n; i++) {
char c = s[i];
pair<char,int> p;
if(c == ')' && !st.empty()) {
p = st.top();
dp[p.second] = 1;
dp[i] = 1;
st.pop();
} else if(c == '(') {
p = {c, i};
st.push(p);
}
}
int result = 0, cur = 0;
for(int i = 0; i < n; i++) {
if(dp[i] == 0) {
cur = 0;
} else {
cur+=1;
result = max(result,cur);
}
}
return result;
}
};