263. Remove Invalid Parentheses
You are given a string s made of lowercase letters plus the bracket characters ( and ). The brackets may not form a balanced sequence.
Delete the smallest possible number of brackets so that what remains is balanced — reading left to right, the running count of ( minus ) never drops below zero and finishes at zero. Letters are never deleted. Return every distinct string that can be produced with that minimum number of deletions.
To keep the answer deterministic, return the strings sorted in ascending lexicographic (dictionary) order. The empty string counts as balanced, so if every bracket has to go, the answer is a list holding one empty string.
Example 1:
Input: s = "()())()"
Output: ["(())()", "()()()"]
Explanation: Exactly one ')' is extra. Deleting the ')' at index 1 yields "(())()"; deleting the one at index 3 or index 4 yields "()()()" (the same string two ways, so it appears once).
Example 2:
Input: s = "(a)())()"
Output: ["(a())()", "(a)()()"]
Explanation: The letter stays put; only one ')' needs to go, and two distinct balanced strings remain.
Example 3:
Input: s = ")("
Output: [""]
Explanation: Neither bracket can be matched, so both must be deleted, leaving the empty string.
Constraints:
- 1 ≤ s.length ≤ 25
- s consists of lowercase English letters and the characters '(' and ')'
- There are at most 20 bracket characters in s
Hints:
How do you test that a bracket string is balanced in one pass? Keep a running balance: +1 for '(', -1 for ')'. The string is balanced exactly when the balance never dips below zero and ends at zero.
One scan tells you the exact minimum: every ')' that arrives when the balance is zero is a forced right-deletion, and whatever positive balance survives to the end is the count of forced left-deletions.
With those two budgets in hand, backtrack over the string: for each bracket decide keep or delete, pruning any branch where a budget goes negative or the balance dips below zero. Collect results in a set to kill duplicates, then sort.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "()())()"
Expected output: ["(())()", "()()()"]