The length of current 'run' is the current position minus the previous unresolved ')' .

For example, ) () () , the length is 4 - 0. if we come to ) ()()() ))))) ()() , then again we do curPos - previous ')'. We use a stack store the characters, match and eliminate '( '. The unmatched ')' is available through st.top().

Before we go through the s string, we first put a dummy ')' with position -1 into the stack.

) () so this case we will get run length 1-(-1 ) = 2.

-1

```
class Solution {
public:
int longestValidParentheses(string s) {
std::stack< pair<char, int> > st;
int max = 0;
st.push( make_pair(')', -1) ); //put a un-matchable ) in the stack
for(int i =0; i < s.size(); i++)
{
if (s[i] == '(') {
st.push( make_pair('(', i));
} else if(s[i] == ')')
{
if(st.top().first == '(' ) //if top is ( then match and cancel
{
st.pop(); //match and cancel the previous (
max = std::max( max, i - st.top().second); get the length of current run and compare with max
} else
{
st.push( make_pair(')', i)); //push
}
}
}
return max;
}
};
```