Remove Invalid Parentheses
Mygate● HardFULLTIMEONSITE INTERVIEWProblem statement
Given a string s containing parentheses and English letters, remove the fewest parentheses necessary to make the remaining parentheses valid. Letters cannot be removed and retain their original order.
A valid string has no prefix containing more closing parentheses than opening parentheses, and its total numbers of opening and closing parentheses are equal.
Return every distinct string attainable using the minimum number of removals, in lexicographic order. Duplicate results appear once. If the original string is valid, return only that string. The empty string is valid.
Function
removeInvalidParentheses(s: String) → List<String>Examples
Example 1
s = "()())()"return = ["(())()","()()()"]Deleting one of the extra closing parentheses yields two distinct valid strings. No zero-removal result is valid.
Example 2
s = "(a)())()"return = ["(a())()","(a)()()"]The letter a is preserved in each of the two minimum-removal results.
Constraints
- 0 ≤ s.length ≤ 20.
- s contains only English letters and the characters ( and ).
- s contains at most 16 parentheses.