Valid Parentheses

This is the most asked stack problem, usually as a warm-up in the first ten minutes. It looks easy, and it is — but interviewers use it to check habits: whether you guard every pop, whether you check the stack at the end, and whether you can explain why a stack and not a counter.

Code editors, compilers and HTML parsers do this check all the time, so it is also a good place to talk about real input.

The problem

You are given a string made only of the characters (, ), [, ], { and }. Return True if it is valid: every opening bracket is closed by a bracket of the same type, brackets close in the right order, and every closing bracket has an opening bracket before it.

• "{[()]}" → True. Each bracket closes the most recent one still open.
• "([)]" → False. The ) arrives while [ is the most recent open bracket.
• "((" → False. Two brackets are never closed.

Constraints: 1 ≤ len(s) ≤ 10⁴, and s holds only the six bracket characters.

Clarifying questions

• Can there be other characters? No, only brackets. (If there were, ignore them; the template in the core lesson does.)
• Is the empty string valid? Yes: nothing is left open.
• Are the three types independent? No: ( must be closed by ), never by ].
• Do you want the position of the error? No, just true or false.

Approach 1: the simple way

A valid string always has at least one adjacent pair like (), [] or {} — the innermost one. Delete all such pairs and repeat. If the string becomes empty, it was valid. If a pass deletes nothing and something is left, it was not.

1def is_valid_by_removal(s: str) -> bool:2    """Delete adjacent matched pairs until nothing changes: O(n^2)."""3    previous = None4    while s != previous:5        previous = s6        s = s.replace("()", "").replace("[]", "").replace("{}", "")7    return s == ""

Time: O(n²). Space: O(n) for the new strings.

Each pass is O(n), and deep nesting forces many passes: ((((…)))) with n / 2 levels loses only one pair per pass, so it needs n / 2 passes. At 10⁴ characters that is 5,000 passes over strings thousands of characters long — tens of millions of character copies. At 10⁶ characters it is hundreds of billions. The waste is that each pass rereads the whole string to find the one pair that became adjacent.

A counter — add one for an opener, subtract one for a closer — is O(n) but wrong: it calls ([)] valid.

The key insight

When a closer arrives, it can only match the most recent opener that is still open. Not any open bracket: the most recent one. That is the nesting rule, and it is exactly what a stack returns.

So keep the unmatched openers on a stack. On an opener, push it: it is work that cannot be finished yet. On a closer, the item on top is the only one it may close. If the top is the matching type, pop it; if the stack is empty or the top is the wrong type, the string is invalid right there. At the end, anything still on the stack was never closed.

The stack also explains the removal approach: popping a matched pair is "deleting the innermost adjacent pair", done at the moment it becomes adjacent, instead of rescanning to find it.

Approach 2: one pass with a stack

1def is_valid(s: str) -> bool:2    """True if every bracket is closed by the right type, in the right order."""3    opener_of = {")": "(", "]": "[", "}": "{"}   # closer -> the opener it needs4    stack: list[str] = []                        # openers still waiting for a partner5    for ch in s:6        if ch in opener_of:                      # a closer7            if not stack or stack.pop() != opener_of[ch]:8                return False                     # nothing open, or the wrong type9        else:10            stack.append(ch)                     # an opener waits11    return not stack                             # leftovers were never closed

The line if not stack or stack.pop() != opener_of[ch] does three things in order. not stack catches a closer with nothing open. Only if the stack is non-empty does stack.pop() run, because or stops at the first true part. Then the popped opener is compared with the one this closer needs.

Dry run on "{[()]}":

And on "([)]":

Time: O(n) — each character is pushed at most once and popped at most once. Space: O(n) — a string of only openers fills the stack.

In real tools — an editor highlighting a bad bracket, a config parser reporting an error — you want where it went wrong, not just False. Push the index with each opener. Then a failed match points at the closer's position, and a leftover at the end points at the unclosed opener, so the error message can say "line 12, column 4" instead of "invalid".

A small speed-up worth mentioning: a string of odd length can never be valid, so if len(s) % 2: return False answers half of all bad inputs without a loop. It does not change the complexity.

Edge cases

• Starts with a closer, like ")(": the stack is empty at the first character, so not stack returns False before any pop.
• Only openers, like "((": the loop never fails; the final not stack is what returns False.
• Empty string: the loop does nothing and the empty stack gives True.
• Wrong type, like "(]": the pop returns (, which is not what ] needs.
• Very deep nesting: 10⁴ openers followed by 10⁴ closers uses a stack of 10⁴ items, which is fine. A recursive checker would pass Python's recursion limit.

Follow-ups

• "Only one bracket type." A counter is enough, and it uses O(1) space. It must never go below zero, and must end at zero:

1def is_valid_single_type(s: str) -> bool:2    """Only ( and ): a counter replaces the stack."""3    open_count = 04    for ch in s:5        open_count += 1 if ch == "(" else -16        if open_count < 0:7            return False                         # a closer with nothing open8    return open_count == 0

• "Remove the fewest brackets to make it valid." Push indices of openers; a closer with an empty stack is marked for removal; openers left at the end are also removed. Still O(n).
• "Length of the longest valid substring." Push indices, and keep the index just before the current valid run at the bottom of the stack (start it with -1). Each match gives a run length of i - stack[-1].