# One pass C++ O(N) solution, using s stack

• class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
int ret = 0;
int temp = 0;
for(int i=0;i<s.length();i++)
{
if(s[i] == '(')
{
stk.push(temp);
temp = 0;
}
else
{
if(stk.empty())
{
temp = 0;
}
else
{
temp += 2;
temp += stk.top();
stk.pop();
if(temp > ret)
{
ret = temp;
}
}
}
}

return ret;
}
};

the basic idea:

1. temp holds temporary maximum length.
2. if s[i] is '(', then push temp to stack, reset temp to 0
3. if s[i] is ')', if stack is empty, it means left of s[i] and right of s[i] are split by s[i] and they will not join together to generate a bigger length, thus reset temp to 0. if stack is not empty, we add 2 to temp because top '(' is joined with s[i] to form a valid parentheses. then we add top of stack to temp as well, if there are any valid parentheses length before the top '(', this is added to temp to get a combined length. every time temp is modified, we update the return value.

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