621. Fewest Bracket Fixes
A code editor receives a line s made of round brackets and lowercase letters. A line is balanced when every ( is closed by a later ) and no ) appears without an earlier unmatched (; letters do not matter.
The editor may delete characters, but it wants to delete as few as possible. Return every different balanced line that can be obtained from s by deleting the minimum possible number of characters. The result may be returned in any order. If s is already balanced, the answer is just s. The answer may contain only letters (or be the empty string) when all brackets must go.
Example 1
- Input:
- s = "(()x)b)"
- Output:
- ["(()x)b","(()xb)","((x)b)"]
- Explanation:
One closing bracket is extra, so exactly one deletion is needed. Three different lines result:
(()x)b,(()xb)and((x)b).
Example 2
- Input:
- s = "a(b)c"
- Output:
- ["a(b)c"]
- Explanation:
The line is already balanced, so nothing is deleted.
Example 3
- Input:
- s = ")))"
- Output:
- [""]
- Explanation:
Every bracket is unmatched, so all three are deleted and the answer is the empty string.
Constraints
- 1 ≤
s.length≤ 14 scontains only(,)and lowercase English letters.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(2^n)
- Space
- O(n)