```
class Solution {
public:
int longestValidParentheses(string s) {
/*
For each open paranthesis, the stack stores the index from where a valid run would start
if we were to close that paranthesis in a valid manner. i.e. for example, in
(()(
the top of the stack would read 1, since, if we manage to find a valid run that closes the
last open paren, we would have a valid run starting from 1 up to wherever we close that paren.
Whereas, in
(()((
the top of the stack would read 3, since if we close that paren, we would have a valid run
starting from index 3 up to the paren that matches it.
*/
std::stack<int> validStartStack;
/*
This variable stores the index from which we have a valid run at present. For example, if we had
)((()()()
this variable would store 3, because we have a valid run starting from index 3. Whereas, if we had
)((()()()(
it would be set to -1 because we are not seeing a valid run
*/
int lastValidStart = -1;
int maxLength = 0;
int i = 0;
for( ; i < s.length(); ++i ) {
if( s[i] == '(' ) {
validStartStack.push( lastValidStart < 0 ? i : lastValidStart );
lastValidStart = -1;
}
else {
if( validStartStack.empty() ) {
lastValidStart = -1;
continue;
}
lastValidStart = validStartStack.top();
int length = i - lastValidStart + 1;
if( length > maxLength )
maxLength = length;
validStartStack.pop();
}
}
return maxLength;
}
};
```