Valid Parentheses

PracticalmediumFree

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

You are given a string of brackets. Across three levels, you'll validate it, locate the first invalid character, then find the longest valid parenthesis substring.

The "last-opened is first-closed" rule is LIFO - every level is a variation on walking the string with a stack.

Level 1 - Basic validation

def is_valid(s: str) -> bool: ...

s contains only ()[]{}. Return True iff every opener has a matching closer of the same kind, in the correct order, and no opener is left unclosed.

Empty string is valid.
A closer with nothing on the stack is invalid.
A closer whose top-of-stack opener doesn't match is invalid.
Anything left on the stack at the end is invalid.

Example:

"()[]{}"  -> True
"([)]"    -> False   # interleaved; '[' is closed by ')' before ']'
"{[]}"    -> True    # correctly nested
"((("     -> False   # unclosed openers
""        -> True    # empty string is valid

Level 2 - Locate the first invalid character

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

Return the index of the first character that breaks the validity invariant, or -1 if the whole string is valid.

A closer with no opener (empty stack), or a closer that mismatches the top -> return the index of the closer.
A string that ends with unclosed openers -> return the index of the earliest opener still on the stack at end of input.

Example:

"({[]})"  -> -1   # fully valid
")"       ->  0   # closer with empty stack
"(]"      ->  1   # mismatched closer at index 1
"([()"    ->  0   # unclosed openers; earliest unmatched opener is at index 0
"()["     ->  2   # valid prefix, then unclosed opener at index 2

The signature lets a parser point users at the exact column of the problem - it's how editor squigglies for unbalanced brackets work.

Level 3 - Longest valid parentheses substring

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

s now contains only ( and ). Return the length of the longest substring that forms a valid parenthesis sequence (LeetCode 32).

Example:

"(()":    2   # "()" at the tail
")()())"  4   # "()()" in the middle
"((()))"  6   # entire string
")(())("  4   # "(())" in the middle

Two classic approaches:

Stack of indices seeded with -1 as a sentinel. Push on (. On ), pop; if the stack is now empty, push i as the new sentinel. Otherwise the current run length is i - stack[-1].
DP: dp[i] = length of the longest valid substring ending at i. Two cases when s[i] == ')': pair with s[i-1] == '(', or close a s[i - dp[i-1] - 1] == '('.

Both run in O(n) time and O(n) space.

Hints

Level 1 - what data structure fits?

The "last-opened is first-closed" rule is LIFO. Reach for a stack.

An opener ((, [, {) gets pushed.
A closer (), ], }) must match the top - pop and verify, else return False.
At end, the stack must be empty.

{ ')': '(', ']': '[', '}': '{' } is cleaner than three if blocks.

Level 2 - what does the stack carry now?

Push (char, index) instead of just the opener. On any failure, return the index of the offending character (the closer). If you exhaust the input with a non-empty stack, return the index from the bottom of the stack - the earliest unmatched opener.

Level 3 - the sentinel trick

Seed the stack with -1. After popping a matched (, the current valid run is i - stack[-1]. If the stack becomes empty after a pop (a ) with no opener), push i as the new sentinel - that's the new "left edge" for subsequent runs.

Mastery checklist

Check	Why it matters
Empty-stack-on-closer guard	A leading closer (`")("`) pops nothing - that's the bug catch
Verify stack empty at end	`"((("` has no mismatches; only the end-of-input check catches it
Map closers -> openers (or vice versa)	One dict beats three `if` blocks
Level 2: push `(char, index)`	Indices flow through the stack alongside the brackets
Level 2: earliest unmatched opener for unclosed input	Bottom of the stack, not the top
Level 3: sentinel `-1` on the stack	Lets `i - stack[-1]` work for the first valid run without a special case
Level 3: re-seed sentinel on a stranded `)`	The new "left edge" is the unmatched closer's index
O(n) time, O(n) space	Single pass; the stack grows at most to the input length

Patterns used

Foundations primers this challenge draws on.

Stacks

Loading editor…

0/3 passed

Level 1 - Basic validation.

Classic stack walk. Openers push, closers must match the top. At the end the stack must be empty.

Level 2 - Locate the first invalid character.

Locked

Pass the previous level to unlock.

Level 3 - Longest valid parentheses substring.

Locked

Pass the previous level to unlock.