Valid Parentheses

A valid string can always be fully reduced by repeatedly deleting any adjacent matching pair — (), [], or {} — until nothing removable is left. If what remains is empty, the string was valid.

class Solution:
    def isValid(self, s: str) -> bool:
        prev_len = -1
        while len(s) != prev_len:
            prev_len = len(s)
            s = s.replace('()', '').replace('[]', '').replace('{}', '')
        return len(s) == 0

Each pass scans the string in O(n), and in the worst case (deeply nested brackets like ((((...))))) it takes O(n) passes to fully collapse — O(n²) total, plus the wasted work of rebuilding a new string on every pass.

Scan left to right with a stack. Every opening bracket gets pushed. Every closing bracket must match whatever is currently on top of the stack — that’s exactly the “most recently opened, must close first” rule, which is what a stack gives you for free.

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}
        stack = []
        for ch in s:
            if ch in pairs:
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:
                stack.append(ch)
        return not stack

Watch the closer-versus-stack-top comparison: a closer that does not match the top stops the scan immediately.

If a closing bracket ever finds a mismatched (or missing) top of stack, we return False immediately — that’s what catches cases like "(]". Complexity: each character is pushed and popped at most once → O(n) time, O(n) space for the stack in the worst case (all openers).