O(n) time and O(1) space python solution


  • 0
    Y

    Scan forwards and backwards to avoid missing '()))))))))' or '((((((((()' case

    class Solution:
        # @param {string} s
        # @return {integer}
        def longestValidParentheses(self, s):
            if not s or len(s) < 2:
                return 0
    
            n = len(s)
            max_len = 0
            start = count = 0
            for i in range(0, n):
                if s[i] == '(':
                    count += 1
                else:
                    count -= 1
                    if count == 0:
                        max_len = max(max_len, i - start + 1)
                    elif count < 0:
                        start = i + 1
                        count = 0
    
            end = n - 1
            count = 0
            for i in reversed(range(0, n)):
                if s[i] == ')':
                    count += 1
                else:
                    count -= 1
                    if count == 0:
                        max_len = max(max_len, end - i + 1)
                    elif count < 0:
                        end = i - 1
                        count = 0
            return max_len

Log in to reply
 

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