Super easy to understand C++ solution with stack

• 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;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.