Remove Invalid Parentheses - Video Solutions

Problem Overview: You receive a string containing letters and parentheses. Some parentheses are invalid. Remove the minimum number of characters so the remaining string forms valid parentheses combinations. Return all possible results that satisfy this constraint.

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

BFS treats each string as a node in a search tree. At each level, remove one parenthesis from every possible position and generate new candidate strings. A queue drives the traversal, and a visited set prevents reprocessing duplicates. The key insight: the first level where you find valid parentheses strings represents the minimum number of removals. Once valid strings appear, stop expanding deeper levels and return all valid candidates from that level. Validity is checked by scanning the string and maintaining a balance counter that increments for ( and decrements for ). BFS works well because it guarantees minimal deletions by exploring states level-by-level. This approach commonly appears in problems involving shortest transformations on strings or graphs, similar to patterns in Breadth-First Search.

Approach 2: DFS with Backtracking (Time: O(2^n), Space: O(n))

DFS solves the problem by recursively deciding whether to remove or keep each parenthesis. First compute how many left and right parentheses must be removed by scanning the string once. The recursive function then explores choices while tracking the current index, remaining removals, and the current balance of open parentheses. Invalid states are pruned immediately: if the balance becomes negative or if removals exceed limits. Duplicate results are avoided using a result set or by skipping identical consecutive removals. The major advantage of DFS is aggressive pruning. Instead of generating every possible substring, the algorithm only explores paths that could still lead to valid strings. This technique relies heavily on patterns from Backtracking and careful state tracking within a string.

Recommended for interviews: BFS is usually the most intuitive answer because it naturally guarantees the minimum number of removals. Many interviewers expect you to reason about the search space and recognize that level-order traversal stops once valid solutions appear. DFS with backtracking demonstrates deeper control over pruning and state management. Showing both approaches signals strong algorithmic understanding: BFS proves you understand optimal search, while DFS highlights your ability to control exponential exploration.