Pattern Guide
Bracket Sequences
"Stack for matching. Count valid sequences. DP for generation. Min removals."
Bracket sequence problems cover: validating balanced parentheses, counting minimum removals to make valid, longest valid substring, generating all valid sequences, and scoring nested structures. The stack is the core tool — push open brackets, pop on close, check match. DP generates/counts valid sequences. Two-pass or stack-based approaches find longest valid substrings.
Problems you can solve with this pattern
6 problems · click any to start solving
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²) |
- 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.