Valid Parentheses

Repeated pair removal

Start with the most literal observation: (), [], and {} are complete pairs. Remove all adjacent complete pairs, then repeat. A valid string eventually becomes empty; an invalid one gets stuck with characters left over.

def is_valid(s: str) -> bool:
    remaining = s
    while True:
        reduced = remaining.replace("()", "").replace("[]", "").replace("{}", "")
        if len(reduced) == len(remaining):
            return reduced == ""
        remaining = reduced

A deeply nested input may expose only one removable pair per pass. Each pass scans a string of up to n characters, and there can be O(n) passes.

Time O(n²) in the worst case. Space O(n) for the rebuilt strings.

Expected-closer stack

A stack is a last-in, first-out collection. That order matches nested brackets: the latest opener must be the first one closed.

You could store openers and translate each closer back to its partner. There's an even cleaner move: store the closer you expect. When ( arrives, push ). When a closer arrives, it must equal the top item. A missing or different top makes the answer false immediately.

def is_valid(s: str) -> bool:
    expected: list[str] = []
    closer_for = {"(": ")", "[": "]", "{": "}"}
 
    for bracket in s:
        if bracket in closer_for:
            expected.append(closer_for[bracket])
        elif not expected or expected.pop() != bracket:
            return False
 
    return not expected

The final emptiness check matters. A string made only of openers never causes a mismatch during the scan, but it still leaves unfinished pairs behind.

Time O(n) — each bracket is pushed or checked once. Space O(n) in the deepest nesting case.