Remove Invalid Parentheses

Remove Invalid Parentheses

What is this problem about?

The Remove Invalid Parentheses interview question asks you to find all possible results of removing the minimum number of parentheses (either ( or )) from a given string to make it valid. A string is valid if all parentheses are properly matched. You must return all unique valid strings of the maximum possible length after removal.

Why is this asked in interviews?

This HARD-level problem is asked at Meta, Microsoft, Amazon, Google, Bloomberg, and Adobe because it demands both optimal constraint satisfaction (minimum removals) and exhaustive search (all valid results). It tests BFS for finding minimum-cost solutions and backtracking for generating all strings at the same cost level. Combining these techniques efficiently is a strong signal of advanced problem-solving ability.

Algorithmic pattern used

The cleanest pattern is BFS level-by-level search. Start with the original string. At each BFS level, generate all strings obtainable by removing exactly one parenthesis from each string in the current level. Validate each generated string. If any valid strings are found at the current level, collect them all and stop (no need to go deeper). This guarantees minimum removals. Use a visited set to avoid processing duplicate strings.

Example explanation

Input: "(a)())()"

Level 0: {"(a)())()"} Level 1 (remove one char): Generate all strings by removing one ( or ). Among them: "(a)()()" — this is valid! Also "(a())()"— valid!

Stop at level 1. Result: ["(a)()()", "(a())()"].

The BFS stops as soon as valid strings appear, guaranteeing minimum removals (1 in this case).

Common mistakes candidates make

• Using DFS without a visited set, generating exponentially many duplicate strings.
• Not stopping BFS immediately after finding valid strings at a level — continuing leads to unnecessarily shorter strings.
• Validating parentheses incorrectly — use a counter that increments on (, decrements on ), and check it never goes negative and ends at 0.
• Removing non-parenthesis characters, which is not allowed.

Interview preparation tip

For the Remove Invalid Parentheses coding problem, the BFS and backtracking interview pattern is essential. Practice writing a clean isValid helper first. Then implement BFS carefully, using a deque and a visited set. Interviewers at Snowflake and Rubrik often ask about the time complexity — in the worst case it is O(n * 2^n), but the visited set and early stopping make it practical. Be ready to discuss why BFS guarantees minimum removals while DFS alone does not.