hardBacktrackingPure DSA~50 min
Fewest Deletions To Balance Parentheses
A user-typed filter expression has stray parentheses. Remove the minimum number of parenthesis characters so the expression becomes valid, and return all distinct results achievable with that minimum number of removals.
Problem
Given a string s containing letters and parentheses, remove the minimum number of invalid parentheses to make the string valid. Return all unique valid strings achievable with that minimum removal count.
Input
A string s of letters, '(' and ')'.
Output
A list of all distinct valid strings with minimal removals.
Constraints
- 1 ≤ |s| ≤ 25
- s contains letters and parentheses only.
- At most 20 parentheses.
Examples
Example 1
Input
s="()())()"
Output
["()()()","(())()"]
Removing one ')' yields both valid strings.
Example 2
Input
s="(a)())()"
Output
["(a)()()","(a())()"]
One removal suffices; letters are untouched.