O(n) time complexity and O(1) space complexity solution in C++


  • 0
    F
    int longestValidParentheses(string s) {
        int n = s.length();
        int cl=0, cr=0;
        int leftStart=-1;
        int rightStart = n;
        int maxLen = 0;
        for(int i=0, k=n-1; i<n, k>=0; ++i, --k) {
            if(s[i] == '(') {
                cl += 1;
            }else if(s[i] == ')' ) {
                cl -= 1;
            }
    
            if( cl==0 ) {   // a valid point
                maxLen = max( i-leftStart, maxLen );
            }else if( cl == -1) { // invalid point
                leftStart = i;
                cl = 0;
            }
    
            //left <-- right
            if(s[k] == ')') {
                cr++;
            }else if(s[k] == '(') {
                cr--;
            }
    
            if(cr==0) {
                maxLen = max( rightStart - k, maxLen);
            }else if(cr == -1) {
                rightStart = k;
                cr = 0;
            }
        }
    
        return maxLen;
    }

Log in to reply
 

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