Valid Parentheses

Given a string of (, ), {, }, [, ], decide whether it is balanced: every opener must have a matching closer in the right order, and the string must not contain interleaved mismatches like ([)].

The key insight: a stack is a perfect model of nesting because of its LIFO discipline. The machine scans left to right; when it sees an opener it pushes it, and when it sees a closer it pops the most recent unmatched opener and checks it matches. If the popped opener does not match, or there is nothing to pop, the string is invalid. At the end, the string is valid only if the stack is empty — otherwise an opener was never closed.

Approach in steps:

1. Map each closer to its matching opener.
2. Scan each character: push openers; on a closer, pop and compare.
3. Return whether the scan finished with an empty stack and no mismatch.

def isValid(s):
    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

Time is O(n), space O(n) in the worst case.

Trickiest edge case: closers without openers — ")))" must return false immediately, so check not stack before popping. The reverse matters too: "(((" scans cleanly but ends with a non-empty stack, which is why the final check is not stack, not "the last comparison matched".