301. Remove Invalid Parentheses
Remove Invalid Parentheses (LeetCode 301) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Parentheses Generation subpattern.
How to solve Remove Invalid Parentheses
Remove Invalid Parentheses is a Generate Valid Parentheses problem, part of Backtracking Patterns. Generate all valid parentheses combinations using backtracking with balance tracking.
Work towards the solution in these steps:
- Since we do not know which brackets can be removed, we try all the options! We can use recursion.
- In the recursion, for each bracket, we can either use it or remove it.
- Recursion will generate all the valid parentheses strings but we want the ones with the least number of parentheses deleted.
The reference solution runs in O(C(n, c)) time and O(c) space.
The Remove Invalid Parentheses solution and editorial walks through the full approach with reference code.
Problem statement
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: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()" Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")(" Output: [""]
Constraints:
- 1 <= s.length <= 25
- s consists of lowercase English letters and parentheses '(' and ')'.
- There will be at most 20 parentheses in s.
Topics and companies
Topics: String, Backtracking, Breadth-First Search.
Reported in interviews at Facebook, Bloomberg, ByteDance, Amazon, Qualtrics.
How to practise Remove Invalid Parentheses on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(C(n, c)) time and O(c) space.
Open Remove Invalid Parentheses in the code editor, or read the Remove Invalid Parentheses editorial for a worked solution with its approach and complexity analysis.
Where Remove Invalid Parentheses sits in the DSA pattern sheet
Problems related to Remove Invalid Parentheses
Other problems that use the same Parentheses Generation and Backtracking Patterns techniques:
- Generate Parentheses — Medium, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern
- Combination Sum II — Medium, same pattern
- Letter Combinations of a Phone Number — Medium, same pattern
Remove Invalid Parentheses FAQ
What is the LeetCode number of Remove Invalid Parentheses?
Remove Invalid Parentheses is LeetCode problem 301, rated Hard.
What pattern is used to solve Remove Invalid Parentheses?
Remove Invalid Parentheses is a Generate Valid Parentheses problem. It belongs to the Backtracking Patterns pattern, in the Parentheses Generation subpattern.
What is the time complexity of Remove Invalid Parentheses?
The reference solution runs in O(C(n, c)) time and O(c) space.
Which companies ask Remove Invalid Parentheses?
Remove Invalid Parentheses has been reported in interviews at Facebook, Bloomberg, ByteDance, Amazon, Qualtrics.