Pattern Reference
Bracket Sequences
"Valid parentheses generation, longest valid parentheses, minimum add to make valid."
Loading...
Deep Dive Tutorial
Bracket problems share a core insight: a valid bracket sequence has, at every prefix, at least as many opens as closes. A stack tracks unmatched opens. For multiple bracket types, the stack must verify that the top matches each closing bracket. For counting problems, think of opens as +1 and closes as -1 — valid sequences are those where the running sum never goes negative and ends at 0.
| Problem Type | Technique | Complexity |
|---|---|---|
| Validate balanced brackets | Stack matching | O(n) |
| Minimum removals to validate | Count unmatched opens + closes | O(n) |
| Longest valid substring | Stack with indices or two-pass | O(n) |
| Generate all valid sequences | Backtracking with open/close counts | O(C_n * n) |
| Score nested brackets | Stack + push/pop layer values | O(n) |
| Count valid subsequences | DP: dp[i][j] = count with i opens unmatched | O(n²) |
Worked Problems
link
Bracket sequence mental models:
- Validation: stack match, O(n)
- Min removals: count unmatched open + unmatched close in two passes
- Longest valid: stack of indices, track "last invalid" position
- Generation: backtracking with (open < n) and (close < open) constraints
- Counting valid: dp[opens_so_far], transitions +1 or -1
Multiple bracket types: Stack must verify each close matches the top. If top is wrong type OR stack empty → invalid.
Nested score / sum: Push layer value on open, merge and multiply on close.
- Validation: stack match, O(n)
- Min removals: count unmatched open + unmatched close in two passes
- Longest valid: stack of indices, track "last invalid" position
- Generation: backtracking with (open < n) and (close < open) constraints
- Counting valid: dp[opens_so_far], transitions +1 or -1
Multiple bracket types: Stack must verify each close matches the top. If top is wrong type OR stack empty → invalid.
Nested score / sum: Push layer value on open, merge and multiply on close.