Longest Valid Parentheses – Solution & Complexity

Q: What is the time and space complexity of Longest Valid Parentheses?

The optimal Longest Valid Parentheses solution runs in `O(n)` time and `O(n)` space. Track indices on a stack (or two directional counting passes) to measure valid runs.

Q: What is the most efficient way to solve Longest Valid Parentheses?

Track indices on a stack (or two directional counting passes) to measure valid runs. This gives `O(n)` time complexity, and is a classic strings, stack, and dynamic programming problem.

Q: How do you solve Longest Valid Parentheses in Python & JavaScript?

We provide a worked Longest Valid Parentheses solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Longest Valid Parentheses an easy or hard interview question?

Longest Valid Parentheses is generally rated **Hard**. It tests strings, stack, and dynamic programming, which are common coding-interview patterns.

1. Track Valid Substring Boundaries

A valid parentheses substring must have every closing parenthesis matched with a previous opening parenthesis.
When a closing parenthesis cannot be matched, any substring crossing it is invalid.
We need a way to remember the most recent invalid boundary and unmatched opening positions.

2. Use a Stack of Indexes

Store indexes rather than characters so lengths are easy to compute.
Start the stack with -1, a sentinel boundary before the string begins.
Push indexes of ( characters because they may match future ) characters.

stack = [-1]
for i, char in enumerate(s):
    if char == '(':
        stack.append(i)

3. Handle Closing Parentheses

For ), pop one index because it attempts to close the most recent unmatched (.
If the stack becomes empty, this ) is unmatched, so push its index as the new invalid boundary.
Otherwise, the current valid substring starts after stack[-1].

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

4. Why the Length Formula Works

After a successful match, stack[-1] is the index just before the current valid substring.
The substring from stack[-1] + 1 through i is therefore valid.
Its length is i - stack[-1].

5. Final Complete Solution

The sentinel handles valid substrings that start at index 0.
Resetting the sentinel after an unmatched ) handles broken regions.
Time complexity is O(n), and extra space complexity is O(n).

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]
    best = 0

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                best = max(best, i - stack[-1])

    return best

Longest Valid Parentheses – Solution & Complexity

1. Track Valid Substring Boundaries

2. Use a Stack of Indexes

3. Handle Closing Parentheses

4. Why the Length Formula Works

5. Final Complete Solution

FAQ

What is the time and space complexity of Longest Valid Parentheses?

What is the most efficient way to solve Longest Valid Parentheses?

How do you solve Longest Valid Parentheses in Python & JavaScript?

Is Longest Valid Parentheses an easy or hard interview question?