Five escalating takes on one bracket string: validate it, point editor squigglies at it, mine the longest valid substring, repair a broken file, and validate with a corruptable wildcard.

Valid Parentheses

PracticalhardFree

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

A linter processes one bracket string through five tools that share a single data-structure insight: the "last-opened is first-closed" rule is LIFO, so every tool is a variation on one stack walk. You build the pipeline: validate it, locate the first error, measure the longest clean section, compute the minimal repair, and survive a wildcard that can impersonate either bracket.

Globally, all functions treat (, [, { as openers and ), ], } as their only closers. Inputs contain no other characters. All functions read the string left to right - none of them may mutate or re-sort the input.

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 -> the whole string is unparseable from the earliest opener still on the stack, so return that opener's index.
Precondition: callers only pass strings of ()[]{} - a character outside that set may raise or return anything; it is never tested.

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.

An empty string or a string with no valid substring returns 0.
Whole string valid means the answer is its full length.

Example:

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

Level 4 - Min-remove repair report

def min_removals_with_example(s: str) -> tuple[int, str]: ...

s again contains only ( and ). A ) is unmatchable if it arrives with no unclosed ( before it; an ( is unmatchable if no ) closes it later. Return a pair: the minimum number of characters to delete so the remainder is valid, and one minimal fixed string - any string reachable by deleting exactly that many characters that passes Level 1's validation.

The minimum count is invariant: every unmatchable ) found left-to-right must go, and every ( left unclosed at the end must go.
Any minimal repair is accepted - (a)b)c-style ambiguity is fine, the checker validates rather than string-matches.
If the string is already valid, return (0, s) unchanged.

Example:

"a)b)c"      -> (2, "abc")        # both stray closers must go
"((et(f)"    -> (2, "et(f)")      # two '(' stay unclosed; letters kept
"(()"        -> (1, "()")         # drop either '(' - both minimal
"))(("       -> (4, "")           # nothing can pair
"lee(t(c)o)de)" -> (1, "lee(t(c)o)de")

(The a, b, e, t letters above are illustrative - see the constraint below.)

Constraint: s may contain lowercase letters and digits alongside (). Non-bracket characters are never removed and never affect validity; the repaired string must keep every non-bracket character in its original relative order.

Level 5 - Wildcard validation

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

s contains only (, ) and *, where each * may be treated as (, ), or empty, independently per occurrence. Validity follows Level 1's rule. Return whether some assignment of the wildcards makes the string valid.

* alone is valid (treat it as empty); "*)" is valid (* as an opener); "(((*)" is not (* can only absorb one )).
Every character must be resolved or matched - an unresolved wildcard is not itself a violation, but unresolved openers/closers are.
Return True/False - no need to produce the witnessing assignment.

Example:

"*)"     -> True    # '*' as an opener pairs with ')'
"(*)"    -> True    # '*' as ''
"(*())"  -> True    # '*' as ''
"((*)"   -> True    # '*' as ')' -> "(())"
"(((*)"  -> False   # even '*' as ')' leaves '((' unclosed
")(*"    -> False   # the leading ')' has no opener before it

Performance requirement

All five functions must be a single left-to-right pass. The grader times each function against inputs up to and including 100_000 characters; the timeout is measured so that any O(n²) fallback (e.g. substring rescans for Level 3, or retrying wildcard assignments) fails. O(n) time and O(n) auxiliary space for every level.

Patterns used

Foundations primers this challenge draws on.

Stacks

Loading editor...

0/5 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.

Level 4 - Min-remove repair report.

Locked

Pass the previous level to unlock.

Level 5 - Wildcard validation.

Locked

Pass the previous level to unlock.