{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Longest Valid Parentheses – Solution & Complexity

Interview solutions
/
Longest Valid Parentheses

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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

FAQ

See also

Practice Longest Valid Parentheses online (run code in the browser)Decode String solution (medium)Decode Ways solution (medium)Edit Distance solution (hard)Longest Common Subsequence solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?