Constant space, O(n) time with forward and backward pass


  • 26
    L

    When right parentheses are more than left parentheses in the forward pass, we can discard previous parentheses. In the backward pass, when left parentheses are more than right parentheses, we can discard previous parentheses.

    int longestValidParentheses(string s) {
        int longest = 0;
        int extra=0;
        int length=0;
        for(int i=0; i<s.size(); i++) {
            if(s[i] == '(') {
                extra++;
                length++;
            }
            else {
                if(extra>0) {
                    extra--;
                    length++;
                    if(extra == 0)
                        longest = max(longest, length);
                }
                else {
                    extra = 0;
                    length=0;
                }
            }
        }
        length = 0;
        extra=0;
        for(int i=s.size()-1; i>=0; i--) {
            if(s[i] == ')') {
                extra++;
                length++;
            }
            else {
                if(extra>0){
                    extra--;
                    length++;
                    if(extra == 0)
                        longest = max(longest, length);
                    
                }
                else {
                    extra = 0;
                    length=0;
                }
            }
        }
        return longest;
    }

  • 1
    L
    //A small optimization: early termination of the right to left pass
    public int longestValidParentheses(String s) {
        char[] sa = s.toCharArray();
        int n = sa.length;
        int sum = 0;
        int max = 0;
        int len = 0;
        int rightMostInvalidRightBracketIndex = -1;
        for (int i = 0; i < n; ++i) {
            if (sa[i] == '(') {
                sum++;
            } else {
                sum--;
            }
            ++len;
            if (sum == 0) {
                max = Math.max(max, len);
            }
            if (sum < 0) {
                sum = 0;
                len = 0;
                rightMostInvalidRightBracketIndex = i;
            }
        }
        sum = 0;
        len = 0;
        for (int i = n-1; i > rightMostInvalidRightBracketIndex; --i) {
            if (sa[i] == ')') {
                sum++;
            } else {
                sum--;
            }
            ++len;
            if (sum == 0) {
                max = Math.max(max, len);
            }
            if (sum < 0) {
                sum = 0;
                len = 0;
            }
        }
        return max;
    }

  • 0
    Y

    I used similar idea here with Python. I am surprised to see not much popularity for this method.

    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            openc,prevV,res,maxl = 0,0,0,0
            for c in s:
                if c=='(': openc += 1
                elif openc:
                    openc -= 1
                    res += 2
                    if not openc:
                        prevV += res
                        res = 0
                        maxl = max(prevV,maxl)
                else: res,prevV = 0,0
            openc,prevV,res = 0,0,0
            for c in s[::-1]:
                if c==')': openc += 1
                elif openc:
                    openc -= 1
                    res += 2
                    if not openc:
                        prevV += res
                        res = 0
                        maxl = max(prevV,maxl)
                else: res,prevV = 0,0
            return maxl
    

  • 0
    A

    yes, I think many solution that need O(n) space do not realize an very important property:
    all invalid left parentheses must be at right side of all invalid right parentheses.
    In fact, information those solution record is useless.


  • 0
    S

    Thanks for sharing, here is bit simplified.

    public int LongestValidParentheses(string srcStr)
        {
            int longest = 0;
            int extra = 0;
            int length = 0;
    
            for (int index = 0; index < srcStr.Length; index++)
            {
                GetLongestStr(srcStr, index, '(', ref extra, ref length, ref longest);
            }
    
            length = 0;
            extra = 0;
    
            for (int index = srcStr.Length - 1; index >= 0; index--)
            {
                GetLongestStr(srcStr, index, ')', ref extra, ref length, ref longest);
            }
    
            return longest;
        }
    
        private void GetLongestStr(string srcStr, int index, char ch, ref int extra, ref int length, ref int longest)
        {
            if (srcStr[index] == ch)
            {
                extra++;
                length++;
            }
            else
            {
                if (extra > 0)
                {
                    extra--;
                    length++;
                    
                    if (extra == 0)
                    {
                        longest = Math.Max(longest, length);
                    }
                }
                else
                {
                    extra = 0;
                    length = 0;
                }
            }
        }
    

Log in to reply
 

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