Valid Parentheses

Find the Index of the First Occurrence in a String

Letter Combinations of a Phone Number

Validate that every bracket closes in the correct order and with the matching type.

Return whether a string containing only parentheses, square brackets, and braces is balanced. Every closing bracket must match the most recent unmatched opening bracket.

**Input / output**
- Input: `s: string`
- Output: boolean

**Examples**
1. `"()[]{}"` returns `true`.
2. `"([)]"` returns `false` because the nesting order is invalid.

**Constraints**
- `0 <= s.length <= 100,000`
- `s` contains only parentheses, square brackets, and braces.

**Follow-up**
Can you reject impossible inputs early, and what information must the stack retain?

- Every opening bracket must be closed by the same bracket type.
- Brackets must close in the reverse order they were opened.
- That reverse-order requirement is the key clue to use a stack.

Understand Valid Nesting

- Counting open and closed brackets can catch some invalid strings.
- It fails for inputs like `(]`, where the counts look balanced but the types do not match.
- We need to remember the exact most recent unmatched opening bracket.

Why Counting Is Not Enough

- Push opening brackets onto a stack.
- When a closing bracket appears, it must match the bracket at the top of the stack.
- If the stack is empty or the type is wrong, the string is invalid immediately.

Use a Stack for Open Brackets

- Store closing-to-opening bracket pairs in a dictionary.
- For each closing bracket, pop the stack and compare it with the expected opener.
- At the end, the stack must be empty for all brackets to be matched.

Handle Closing Brackets

- The final algorithm scans the string once and uses the stack to enforce correct order.
- Time complexity is O(n), where `n` is the length of the string.
- Space complexity is O(n) in the worst case when all characters are opening brackets.