Problem Statement in English

You’re given a string containing just the characters ‘(’ and ‘)’. Find the length of the longest valid (well-formed) parentheses substring.

Approach

Since we can’t brute force it, we can use a two-pass approach.

A substring of parentheses is valid if:

  • The total number of ( equals the total number of ).
  • At no point while reading left-to-right does ) exceed (.
  • At no point while reading right-to-left does ( exceed ).

In the first pass, we traverse the string from left to right, counting the number of opening and closing parentheses. If at any point the number of closing parentheses exceeds the number of opening parentheses, we reset our counts. If the counts are equal, we update our maximum length.

In the second pass, we traverse the string from right to left, counting the number of opening and closing parentheses. If at any point the number of opening parentheses exceeds the number of closing parentheses, we reset our counts. If the counts are equal, we update our maximum length.

After both passes, we return the maximum length found.

And we’re done!

Solution in Python


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        opening = closing = max_len = 0
        
        # left to right
        for char in s:
            if char == '(':
                opening += 1
            else:
                closing += 1

            if opening == closing:
                max_len = max(max_len, 2 * closing)
            elif closing > opening:
                opening = closing = 0
                
        opening = closing = 0
        # right to left
        for char in reversed(s):
            if char == '(':
                opening += 1
            else:
                closing += 1

            if opening == closing:
                max_len = max(max_len, 2 * closing)
            elif opening > closing:
                opening = closing = 0
                
        return max_len

Complexity

  • Time: $O(n)$
    Since we are traversing the string twice, the time complexity is linear with respect to the length of the string.

  • Space: $O(1)$
    Since we are using a constant amount of space for variables, the space complexity is constant.

Mistakes I Made

I brute forced it :(

And we are done.