Remove Invalid Parentheses
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.
Example 1
Input
s = "()())()"Output
["(())()","()()()"]Removing one invalid closing parenthesis can produce either
(())() or ()()(), and both are valid with the minimum number of removals.Example 2
Input
s = "(a)())()"Output
["(a())()","(a)()()"]Removing one invalid closing parenthesis can produce either
(a())() or (a)()(), and both are valid with the minimum number of removals.Constraints
- 1 <= s.length <= 25
- s consists of lowercase English letters and parentheses '(' and ')'.
- There will be at most 20 parentheses in s.
Asked at 10 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.