My solution O(n) using stack store valid length


  • 0
    R
    int longestValidParentheses(string s) {
           stack<int> stk;
           // cur is curent length of valid parentheses string
           int i = 0, j = 0, n = s.size(), cur = 0, longest = 0;
           for (; i < n; ++i)
           {
               if (s[i] == '(')
                {
                    stk.push(cur);
                    longest = max(longest, cur);
                    cur = 0;
                }
                else if (s[i] == ')')
                {
                    if (stk.size() > 0)
                    {
                        cur += stk.top() + 2;  //previous valid length + valid length in stack + current length increment
                        stk.pop();
                    }
                    else
                    {
                        longest = max(longest, cur);
                        cur = 0;
                    }
                }
            }
            return max(cur, longest);
        }
    

Log in to reply
 

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