Is Remove Invalid Parentheses easy or hard?

Remove Invalid Parentheses is classified as a Hard problem because it combines exponential search with pruning and duplicate handling. Candidates must design a strategy that guarantees minimum removals while generating all valid outputs.

Remove Invalid Parentheses Python/Java solution

Python and C++ solutions commonly use BFS with a queue and visited set. Java and JavaScript implementations often demonstrate DFS with backtracking, tracking remaining removals and open parentheses counts to maintain validity.

How to solve Remove Invalid Parentheses in O(n)?

An O(n) solution does not exist because the problem requires generating all valid results after removing parentheses. In the worst case, exponentially many combinations must be explored. The optimal practical strategies are BFS or DFS with pruning, both with O(2^n) complexity.

What is the best approach for Remove Invalid Parentheses?

Breadth-First Search (BFS) is widely considered the most intuitive approach because it explores strings by number of removals. The first level that produces valid strings guarantees the minimum number of removals. Depth-First Search with backtracking is also popular because it prunes invalid states while constructing valid strings.

Is Remove Invalid Parentheses asked at Google/Amazon/Meta?

Remove Invalid Parentheses has appeared in interviews at large tech companies including Google, Meta, and Amazon. The problem tests search strategies, pruning techniques, and understanding of BFS versus DFS state exploration.

What data structure is used in Remove Invalid Parentheses?

Common implementations use a queue and hash set for BFS to track visited strings and avoid duplicates. DFS solutions rely on recursion, backtracking state variables, and sometimes a set to store unique results.

What is the time complexity of Remove Invalid Parentheses?

Both BFS and DFS with backtracking have worst-case time complexity of O(2^n). Each character can potentially be removed or kept, producing an exponential number of candidate strings. Space complexity is also O(2^n) due to storing generated states or recursion paths.

Description Hints 4 Solution Video 23:20

301. Remove Invalid Parentheses

Hard52.4% acceptance10 companies

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.

Asked at 10 companies

Deliveroo Millennium Meta Tiktok Rubrik Microsoft Oracle

Google Amazon Bloomberg

Topics

Hints open one at a time

Hint 1

Since we do not know which brackets can be removed, we try all the options! We can use recursion.

Hint 2

In the recursion, for each bracket, we can either use it or remove it.

Hint 3

Recursion will generate all the valid parentheses strings but we want the ones with the least number of parentheses deleted.

Hint 4

We can count the number of invalid brackets to be deleted and only generate the valid strings in the recusrion.

23:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution