C++ O(n) time solution beats 84%


  • 0
    Z
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int count=0,length=0,longest=0,i;
            for(i=0;i<s.length();i++)
            {
                if(s[i]=='(')
                    {
                        count++;
                        continue;
                    }
                else {
                    if(count!=0)
                    {
                        count--;
                        length++;
                        if(count==0)
                            longest=length>longest?length:longest;
                    }
                    else{
                        length=0;
                        count=0;
                    }
                }
            }
            length=0;
            count=0;
            for(i=s.length()-1;i>=0;i--)
            {
                if(s[i]==')')
                    {
                        count++;
                        continue;
                    }
                else {
                    if(count!=0)
                    {
                        count--;
                        length++;
                        if(count==0)
                           longest=length>longest?length:longest;
                    }
                    else{
                        length=0;
                        count=0;
                    }
                }
            }
            return 2*longest;
        }
    };
    

Log in to reply
 

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