LeetCode 32 - Longest Valid Parentheses

The problem asks us to find the length of the longest contiguous substring that forms a valid parentheses sequence. A valid parentheses sequence is one where every opening parenthesis '(' has a corresponding closing parenthesis ')', and the pairs are correctly nested.

leetcodehardstringdynamic-programmingstack

LeetCode Problem 32

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming, Stack

Solution

Problem Understanding

The problem asks us to find the length of the longest contiguous substring that forms a valid parentheses sequence. A valid parentheses sequence is one where every opening parenthesis '(' has a corresponding closing parenthesis ')', and the pairs are correctly nested.

For example, the string "()()" is valid because each opening parenthesis is matched properly. The string "(())" is also valid because nested pairs are allowed. However, strings like "(()" or ")(" are not fully valid because some parentheses remain unmatched.

The input is a single string s containing only two possible characters, '(' and ')'. The output should be an integer representing the maximum length of any contiguous valid parentheses substring.

The constraints are important:

  • The string length can be as large as 3 * 10^4
  • Only parentheses characters are present

These constraints immediately tell us that inefficient solutions, especially anything with cubic complexity, will likely time out. We need an algorithm that is at worst linear or close to linear.

Several edge cases are especially important:

  • An empty string should return 0
  • A string with only '(' or only ')' should return 0
  • Strings with unmatched parentheses at the beginning or end can still contain valid substrings inside
  • Nested valid structures such as "((()))" must be handled correctly
  • Consecutive valid structures such as "()()()" should be combined into a larger valid length

The key challenge is determining how to efficiently track matching parentheses while ensuring the substring remains contiguous and well-formed.

Approaches

Brute Force Approach

The most straightforward solution is to examine every possible substring and determine whether it forms a valid parentheses sequence.

We can generate all substrings using two nested loops. For each substring, we check validity using a balance counter:

  • Increment for '('
  • Decrement for ')'
  • If the balance ever becomes negative, the substring is invalid
  • At the end, balance must equal zero for the substring to be valid

Whenever we find a valid substring, we update the maximum length.

This approach is correct because it explicitly checks every possible candidate substring. However, it is far too slow for the given constraints. There are O(n^2) substrings, and validating each substring may take O(n) time, leading to O(n^3) complexity overall.

With n = 30000, this is completely impractical.

Key Insight for the Optimal Solution

The important observation is that we do not need to repeatedly validate entire substrings from scratch.

Instead, we can process the string once while keeping track of unmatched parentheses positions using a stack.

The core idea is:

  • Push indices of opening parentheses onto the stack
  • When encountering a closing parenthesis, attempt to match it with the most recent unmatched opening parenthesis
  • If a match exists, compute the length of the current valid substring
  • If no match exists, mark the current position as a new boundary

Using indices instead of characters allows us to directly compute substring lengths efficiently.

This transforms the problem into a linear-time scan.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every substring individually
Optimal Stack Solution O(n) O(n) Uses stack of indices to track unmatched parentheses

Algorithm Walkthrough

Optimal Stack Algorithm

  1. Initialize a stack with the value -1.

The stack stores indices, not characters. The initial -1 acts as a sentinel boundary before the string starts. This helps compute lengths correctly when a valid substring begins at index 0. 2. Initialize a variable max_length = 0.

This variable keeps track of the longest valid substring found so far. 3. Traverse the string character by character using index i.

We need indices because substring lengths are computed using index differences. 4. If the current character is '(', push its index onto the stack.

Opening parentheses may potentially match future closing parentheses, so we store their positions. 5. If the current character is ')', pop from the stack.

This represents attempting to match the current closing parenthesis with the most recent unmatched opening parenthesis. 6. After popping, check whether the stack is empty.

If the stack becomes empty, it means there was no matching opening parenthesis for the current closing parenthesis. In this case, push the current index as a new boundary marker. 7. If the stack is not empty after popping, compute the current valid substring length.

The length is:

$\text{current length} = i - \text{stack.top}$

The stack top now represents the index before the start of the current valid substring. 8. Update max_length if the current valid length is larger. 9. Continue until the entire string has been processed. 10. Return max_length.

Why it works

The stack always maintains indices of unmatched parentheses boundaries. Whenever a valid match is formed, the difference between the current index and the stack's top gives the length of the largest valid substring ending at the current position.

The sentinel value and unmatched closing parentheses ensure that invalid regions correctly reset substring boundaries. This invariant guarantees that every valid substring length is computed accurately exactly once.

Python Solution

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

        for index, char in enumerate(s):
            if char == '(':
                stack.append(index)
            else:
                stack.pop()

                if not stack:
                    stack.append(index)
                else:
                    current_length = index - stack[-1]
                    max_length = max(max_length, current_length)

        return max_length

The implementation begins by initializing the stack with -1. This sentinel value simplifies boundary calculations and avoids special-case logic for valid substrings beginning at index 0.

As we iterate through the string, opening parentheses indices are pushed onto the stack because they may later participate in a valid pair.

When a closing parenthesis appears, we pop from the stack to represent matching it with the most recent unmatched opening parenthesis.

If the stack becomes empty after popping, the current closing parenthesis has no valid match. We therefore push its index as a new invalid boundary.

Otherwise, the substring between the current index and the new stack top is valid. We compute its length and update the maximum answer.

The algorithm processes each character exactly once, making it highly efficient.

Go Solution

func longestValidParentheses(s string) int {
    stack := []int{-1}
    maxLength := 0

    for i, ch := range s {
        if ch == '(' {
            stack = append(stack, i)
        } else {
            stack = stack[:len(stack)-1]

            if len(stack) == 0 {
                stack = append(stack, i)
            } else {
                currentLength := i - stack[len(stack)-1]

                if currentLength > maxLength {
                    maxLength = currentLength
                }
            }
        }
    }

    return maxLength
}

The Go implementation follows the same logic as the Python version but uses slices to simulate a stack.

Appending to the slice pushes an element, while slicing with stack[:len(stack)-1] removes the top element.

Go strings are UTF-8 encoded, but since the input only contains ASCII parentheses characters, iterating with range is safe and efficient.

No integer overflow concerns exist because the maximum string length is only 30000.

Worked Examples

Example 1

Input:

s = "(()"
Index Character Stack Before Action Stack After Current Max
Start - [-1] Initialize [-1] 0
0 ( [-1] Push index [-1, 0] 0
1 ( [-1, 0] Push index [-1, 0, 1] 0
2 ) [-1, 0, 1] Pop and compute length [-1, 0] 2

The longest valid substring is "()", length 2.

Example 2

Input:

s = ")()())"
Index Character Stack Before Action Stack After Current Max
Start - [-1] Initialize [-1] 0
0 ) [-1] Pop, stack empty, push boundary [0] 0
1 ( [0] Push index [0, 1] 0
2 ) [0, 1] Pop and compute [0] 2
3 ( [0] Push index [0, 3] 2
4 ) [0, 3] Pop and compute [0] 4
5 ) [0] Pop, stack empty, push boundary [5] 4

The longest valid substring is "()()", length 4.

Example 3

Input:

s = ""

The loop never executes because the string is empty.

Result:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is pushed and popped at most once
Space O(n) Stack may store all indices in the worst case

The algorithm is linear because every index enters and leaves the stack at most one time. No nested rescanning occurs.

The worst-case space usage occurs for strings like "(((((((", where every index remains in the stack.

Test Cases

solution = Solution()

assert solution.longestValidParentheses("(()") == 2  # basic partial match
assert solution.longestValidParentheses(")()())") == 4  # multiple valid groups
assert solution.longestValidParentheses("") == 0  # empty string
assert solution.longestValidParentheses("(") == 0  # single opening parenthesis
assert solution.longestValidParentheses(")") == 0  # single closing parenthesis
assert solution.longestValidParentheses("()") == 2  # simplest valid pair
assert solution.longestValidParentheses("(())") == 4  # nested valid structure
assert solution.longestValidParentheses("()()") == 4  # consecutive valid pairs
assert solution.longestValidParentheses("(((())))") == 8  # deeply nested structure
assert solution.longestValidParentheses("(()())") == 6  # mixed nesting and adjacency
assert solution.longestValidParentheses("(((((") == 0  # all opening parentheses
assert solution.longestValidParentheses(")))))") == 0  # all closing parentheses
assert solution.longestValidParentheses("())") == 2  # unmatched closing at end
assert solution.longestValidParentheses("(()))(") == 4  # unmatched parentheses on both ends
assert solution.longestValidParentheses("()(())") == 6  # combined structures
assert solution.longestValidParentheses("(()(()))") == 8  # complex nesting
Test Why
"(()" Verifies partial valid substring
")()())" Tests invalid prefixes and multiple groups
"" Validates empty input handling
"(" Single unmatched opening parenthesis
")" Single unmatched closing parenthesis
"()" Smallest valid input
"(())" Tests nested structure
"()()" Tests adjacent valid groups
"(((())))" Deep nesting stress test
"(()())" Mixed nested and sequential pairs
"(((((" No valid substring exists
")))))" All invalid closing parentheses
"())" Invalid suffix handling
"(()))(" Invalid characters at both ends
"()(())" Combined valid regions
"(()(()))" More complex balanced nesting

Edge Cases

One important edge case is the empty string. A naive implementation might accidentally assume at least one character exists and attempt invalid stack operations. In this solution, the loop simply never executes, and max_length remains 0, which is the correct result.

Another critical edge case is strings that begin with unmatched closing parentheses, such as ")()())". Without careful boundary handling, substring lengths could become negative or incorrectly span invalid regions. The sentinel and boundary reset logic solve this problem by pushing the index of unmatched closing parentheses onto the stack.

A third important case involves deeply nested valid structures such as "(((())))". Some incorrect implementations only handle adjacent pairs and fail to properly merge nested regions. This stack-based approach naturally handles nesting because each closing parenthesis matches the most recent unmatched opening parenthesis.

A fourth subtle case is multiple consecutive valid regions, such as "()()" or "()(())". The algorithm correctly combines adjacent valid sequences because the stack maintains the boundary before the start of the current valid substring, allowing lengths to extend across multiple matched pairs.