Sharing my 8ms C++ solution


  • 0
    T
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int n=s.length();
            if(n<=1)
                return 0;
                
            // take out an effetice substring with '(' as the start and ')' as the end     
            int start=0, end=n-1;
            while(s[start]==')')
            {
                start++;
            }
            while(s[end] == '(')
            {
                end--;
            }
            if(end-start<1)
                return 0;
                
            int i, pos, sum, maxlen, maxlen2;
            
            // from left to right
            pos=start;
            sum=0;
            maxlen=0;
            for(i=start; i<=end; i++)
            {
                if(s[i] == '(') // '('->-1 and ')'->1
                    sum = sum - 1;
                else
                    sum = sum + 1;
                    
                if(sum>0)
                {
                    pos = i + 1;
                    sum = 0;
                }
                
                if(sum==0)
                {
                    maxlen = max(maxlen, i-pos+1);
                }
            }
            
            // from right to left
            pos = end;
            sum = 0;
            maxlen2=0;
            for(i=end; i>=start; i--)
            {
                if(s[i] == '(')
                    sum = sum - 1;
                else
                    sum = sum + 1;
                
                if(sum<0)
                {
                    pos = i-1;
                    sum = 0;
                }
                
                if(sum==0)
                {
                    maxlen = max(maxlen, pos-i+1);
                }
            }
            
            int result;
            result = max(maxlen, maxlen2);
            return result;
        }

Log in to reply
 

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