Fewest Deletions to Balance
HardBacktracking
Problem
A string s contains round brackets ( ) and lowercase letters. It is balanced if, ignoring letters, the brackets are well nested (no prefix closes more than it opened, and the totals match).
Delete the minimum number of brackets to make s balanced, and return every distinct string you can obtain with that minimum number of deletions, in any order. Letters are never deleted.
Example 1
- Input:
- s = "()())()"
- Output:
- ["(())()", "()()()"]
One deletion is necessary; removing either of two different ')' gives these two distinct results.
Example 2
- Input:
- s = ")("
- Output:
- [""]
Both brackets must go, leaving the empty string.
Constraints
- 1 ≤ s.length ≤ 25
- s contains '(', ')' and lowercase letters.
- At most 20 brackets in s.
Hint
Show the first hint
Before searching, can you compute exactly how many '(' and how many ')' must be deleted?
Walkthrough
How to approach it
01Clarify before coding
- Can letters be deleted? No, only brackets.
- Must the answers be distinct? Yes; deleting either of two adjacent ')' gives the same string, reported once.
- Is the empty string a valid answer? Yes, when every bracket must go.
02Brute force
BFS by levels: remove one bracket in every possible way, then two, and so on, stopping at the first level that contains balanced strings.
Cost: Up to C(b, d) strings at level d for b brackets, each checked in O(n), with a set to deduplicate: workable but explores many unbalanced intermediate strings.
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.
This problem is part of Pro.