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


  • 1
    J
    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.

Log in to reply
 

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