LeetCode 32: Longest Valid Parentheses

Problem Restatement

We are given a string s containing only two characters:

"("
")"

We need to return the length of the longest valid parentheses substring.

A valid parentheses substring must be continuous, balanced, and well-formed.

Examples of valid strings:

"()"
"(())"
"()()"
"(()())"

Examples of invalid strings:

"("
")("
"(()"
"())"

If there is no valid parentheses substring, return 0.

The constraints allow an empty string, and the length can be up to 3 * 10^4. The string contains only '(' and ')'.

Input and Output

Function shape:

def longestValidParentheses(s: str) -> int:
    ...

Examples

Example 1:

s = "(()"

The longest valid substring is:

"()"

Its length is:

2

Return:

2

Example 2:

s = ")()())"

The longest valid substring is:

"()()"

Its length is:

4

Return:

4

Example 3:

s = ""

There are no characters, so there is no valid parentheses substring.

Return:

0

First Thought: Check Every Substring

A direct solution is to check every substring.

For each starting index i, try every ending index j.

For each substring s[i:j], check whether it is valid.

A substring is valid when:

1. Its balance never goes below 0.
2. Its final balance is 0.

Here, balance means:

"(" adds 1
")" subtracts 1

Code:

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        best = 0

        for left in range(n):
            balance = 0

            for right in range(left, n):
                if s[right] == "(":
                    balance += 1
                else:
                    balance -= 1

                if balance < 0:
                    break

                if balance == 0:
                    best = max(best, right - left + 1)

        return best

This is correct, but it is too slow for large input.

Problem With Brute Force

There are many substrings.

For a string of length n, there are about:

n * n

possible start and end pairs.

For each starting index, we may scan many characters.

With n = 30000, this can be far too slow.

We need a linear solution.

Key Insight

A valid parentheses substring ends when a ")" matches a previous "(".

So we need to remember the indices of unmatched opening parentheses.

A stack is a good fit.

But we also need to know where the current valid region starts.

For that, keep a base index.

The base index is the position before the current possible valid substring.

We initialize the stack with:

[-1]

This means a valid substring starting at index 0 has length:

i - (-1)

For example, if we reach index 1 in "()", the length is:

1 - (-1) = 2

Algorithm

Use a stack of indices.

Initialize:

stack = [-1]
best = 0

Then scan the string from left to right.

If the current character is "(", push its index.

stack.append(i)

If the current character is ")":

1. Pop one index from the stack.
2. If the stack becomes empty, push the current index as the new base.
3. Otherwise, the current valid length is i - stack[-1].

Why this works:

When a ")" matches a previous "(", popping removes the matched opening parenthesis.

The top of the stack after popping is now the index before the current valid substring.

So the valid length is:

i - stack[-1]

Correctness

The stack stores indices that block or start valid substrings.

At the beginning, -1 acts as the base before index 0.

When we see "(", we push its index because it may match a future ")".

When we see ")", we pop one index. If the popped index was an opening parenthesis, then this ")" matched it.

After the pop, if the stack still has an index, then stack[-1] is the position before the longest valid substring ending at the current index. Therefore, i - stack[-1] gives the length of that valid substring.

If the stack becomes empty, then the current ")" has no matching "(". No valid substring can cross this index. We push the current index as the new base.

The algorithm checks every index once. Whenever a valid substring ends, its length is considered. Therefore, the maximum stored in best is the length of the longest valid parentheses substring.

Complexity

Implementation

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        best = 0

        for i, ch in enumerate(s):
            if ch == "(":
                stack.append(i)
            else:
                stack.pop()

                if not stack:
                    stack.append(i)
                else:
                    best = max(best, i - stack[-1])

        return best

Code Explanation

We start with a stack containing -1.

stack = [-1]

This lets us measure valid substrings that start at index 0.

The answer starts at 0.

best = 0

Then we scan the string.

for i, ch in enumerate(s):

For an opening parenthesis, push its index.

if ch == "(":
    stack.append(i)

For a closing parenthesis, pop one index.

else:
    stack.pop()

If the stack becomes empty, this closing parenthesis cannot be part of any valid substring crossing this index.

So we set this index as the new base.

if not stack:
    stack.append(i)

Otherwise, the substring after stack[-1] up to i is valid.

best = max(best, i - stack[-1])

Finally, return best.

Testing

def check(s: str, expected: int) -> None:
    actual = Solution().longestValidParentheses(s)
    assert actual == expected, (s, actual, expected)

def run_tests():
    check("(()", 2)
    check(")()())", 4)
    check("", 0)
    check("()", 2)
    check("()()", 4)
    check("(())", 4)
    check("())", 2)
    check("(((", 0)
    check(")))", 0)
    check("()(())", 6)
    check(")()())()()(", 4)

    print("all tests passed")

run_tests()

Test meaning: