Remove Invalid Parentheses - Video Solutions

Problem Overview: Given a string containing letters and parentheses, remove the minimum number of invalid parentheses so the resulting string becomes valid. Return all possible valid results without duplicates.

Approach 1: Breadth-First Search (BFS) (Time: O(2^n), Space: O(2^n))

The BFS approach treats each string as a node in a search graph. Start with the original string and generate the next level by removing one parenthesis at every possible position. For each generated string, check validity using a counter: increment for (, decrement for ), and ensure the count never drops below zero. The key insight is that BFS explores by number of removals. As soon as valid strings appear at a level, stop exploring deeper levels because they would require more removals than necessary. Use a queue for traversal and a set to avoid revisiting strings. This guarantees the results contain the minimum number of removals. The method works well for problems where the smallest transformation must be discovered first. Concepts rely heavily on Breadth-First Search and efficient string manipulation.

Approach 2: Depth-First Search with Backtracking (Time: O(2^n), Space: O(2^n))

This method first calculates how many left and right parentheses must be removed. Then perform a DFS that decides for each character whether to keep it or remove it. Maintain counts for open parentheses and remaining removals. When adding characters to the current path, ensure validity rules: the number of closing parentheses never exceeds opening ones. If a parenthesis is removed, decrease the appropriate removal counter. Backtracking explores all valid constructions while pruning branches that would create invalid states. A set is often used to deduplicate results. Compared with BFS, DFS generates results by constructing valid strings directly instead of exploring all intermediate states. This technique demonstrates strong understanding of backtracking and recursion pruning strategies.

Recommended for interviews: BFS is usually the most intuitive explanation because it naturally guarantees the minimum removals. Many candidates start there to show correctness reasoning. DFS with backtracking is often considered the stronger solution once you compute the exact number of parentheses that must be removed. It reduces unnecessary states and demonstrates pruning, recursion control, and deeper algorithmic thinking. Interviewers typically expect one of these two strategies with correct duplicate handling and a clear validity check.