C++,O(n)time and O(1)space


  • 5
    Q

    Let '(' equals to 1 and ')' equals to -1,if s.substr(i,j-i+1) is a valid parentheses,then the sum of this substring should be 0.

     int longestValidParentheses(string s) {
            int n=s.length();
            if(n<=1)
                return 0;
            int i=0,j=n-1;
            while(s[i]==')')
                i++;
            while(s[j]=='(')
                j--;
            s=s.substr(i,j-i+1);  
            n=s.length();
            if(n<=1)
                return 0;
            int ans=0,maxlen=0,pos=0,maxlen1=0;
            for(i=0;i<n;i++)
            {
                int tmp=s[i]=='('?1:-1;
                ans+=tmp;
                if(ans<0)
                {
                    pos=i+1;
                    ans=0;
                }
                else if(ans==0)
                    maxlen=max(maxlen,i-pos+1);
            }
            ans=0;
            pos=n-1;
            for(i=n-1;i>=0;i--)
            {
                int tmp=s[i]=='('?1:-1;
                ans+=tmp;
                if(ans>0)
                {
                    pos=i-1;
                    ans=0;
                }
                else if(ans==0)
                    maxlen1=max(maxlen1,pos-i+1);
            }
            ans= max(maxlen,maxlen1);
            return ans;
    }

Log in to reply
 

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