Every Smallest Bracket Repair
text holds lowercase letters and the brackets ( and ). Remove as few brackets as possible so that the brackets left are balanced: every ) closes an earlier (, and every ( gets closed. Letters are never removed.
Return every different string this can leave, in any order.
Example 1
text "(a)b)"
returns ["(a)b","(ab)"]
There is one ) too many. Removing the last one leaves (a)b, removing the first one leaves (ab).
Example 2
text ")x("
returns ["x"]
Neither bracket can be matched, so both are removed.
Example 3
text "(()"
returns ["()"]
Removing either ( leaves the same string, so it is listed once.
Constraints
1 <= len(text) <= 16textholds lowercase letters,(and)only
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.