Bracket Balance Check
EasyStackFree
Problem
A configuration linter receives a string s made only of the characters (, ), [, ], { and }.
The string is balanced when every opening bracket is closed by a bracket of the same kind, and brackets close in the reverse order they were opened. Return true if s is balanced and false otherwise. The empty string is balanced.
Example 1
- Input:
- s = "([]{})"
- Output:
- true
[ ] closes inside ( ), then { } opens and closes, then ) closes the outer pair.
Example 2
- Input:
- s = "([)]"
- Output:
- false
The ) arrives while [ is still the most recent open bracket, so the nesting is crossed.
Example 3
- Input:
- s = "(("
- Output:
- false
Constraints
- 0 ≤ s.length ≤ 10^4
- s contains only ()[]{}
Hint
Show the first hint
When a closing bracket arrives, which opening bracket must it match?
Walkthrough
How to approach it
01Clarify before coding
- Can other characters appear? No, only the six bracket characters.
- Is the empty string balanced? Yes, return true.
- Is "([)]" acceptable because counts match? No: order matters, not only counts.
02Brute force
Repeatedly delete any adjacent matching pair "()", "[]" or "{}" until nothing changes; the string is balanced if it ends empty.
Cost: Each pass is O(n) and removes at least one pair, so up to n/2 passes: O(n²) time, plus a new string per pass.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.