Solution: Remove Invalid Parentheses

Statement

You are given a string, s, that contains:

• Lowercase English letters

• Opening '(' and closing ')' parentheses

A string is considered valid if:

1. All opening parentheses '(' are closed properly by a matching ')'.

2. The parentheses are in the correct order and nesting.

3. Letters can appear anywhere and do not affect validity.

Return all possible valid strings that can be formed by removing the minimum number of invalid parentheses. The answer must be a list of unique strings, in any order.

Constraints:

• $1 \leq$ s.length $\leq 25$

• s consists of lowercase English letters and parentheses '(' and ')'.

• There will be at most 20 parentheses in s.

Solution

The algorithm aims to generate all possible valid strings by removing the minimum number of invalid parentheses. It starts with a preprocessing step to determine how many opening and closing parentheses need to be removed. As it scans the string, it increments a counter for each opening parenthesis. For each closing parenthesis, it tries to match it with an opening one. If no match is found, it marks the closing parenthesis as unmatched. This ensures the algorithm knows the minimum number of each type of parenthesis to remove.

Once the number of invalid parentheses is known, the algorithm uses recursive backtracking to explore all valid combinations. It processes the string one character at a time and considers several choices:

• If the character is an opening parenthesis (, the algorithm considers two choices: skip it to reduce the number of unmatched openings, or add it to the expression and increase the open count.

• If it’s a closing parenthesis ), it can be skipped to reduce unmatched closings, or added to the expression—but only if more opening parentheses are already added, to keep the expression balanced.

• If it’s a non-parenthesis character, it is always added to the current expression.

The recursion continues until the end of the string is reached. At that point, if the number of opening and closing parentheses is equal (i.e., the expression is balanced) and no more removals are needed, the expression is added to a result set to ensure uniqueness. After exploring all possibilities, the algorithm returns all unique valid expressions as a list.

The steps of the algorithm are as follows:

1. Count the minimum invalid parentheses to remove:

   1. Initialize two counters, leftToRemove (Number of extra '(' to remove) and rightToRemove (Number of extra ')' to remove).

   2. Iterate through the string:

      1. If the character is '(', increment leftToRemove.

      2. If the character is ')':

         1. If leftToRemove > 0, a matching '(' exists, so decrement leftToRemove.

         2. Else, increment rightToRemove (unmatched right parenthesis).

2. We define a recursive helper function, backtrack(index, openCount, closeCount, path, leftRemain, rightRemain) to explore all valid combinations of the input string. index is the current position in the string. openCount and closeCount track the number of '(' and ')' in the current path to maintain balance. path holds the built string so far. leftRemain and rightRemain indicate how many '(' and ')' can still be removed to form a valid expression.

• When the end of the string is reached (i.e., index == len(s)), check if no removals remain (leftRemain == 0 and rightRemain == 0) and the parentheses are balanced (open_count == close_count). If so, add the current path to the result set.

• Recursive case: At each character char = s[index]:

1. If char == '(':

   1. Option to remove it (if leftRemain > 0):

      1. Recurse without adding '(', decrementing leftRemain.

   2. Option to keep it:

      1. Recurse adding '(' to path, incrementing openCount.

2. If char == ')':

   1. Option to remove it (if rightRemain > 0):

      1. Recurse without adding ')', decrementing rightRemain.

   2. Option to keep it:

      1. Only if closeCount < openCount (to ensure balance).

      2. Recurse adding ')', incrementing closeCount.

3. If char is not a parenthesis:

   1. Always keep it and recurse with the character added to path.

3. Call backtrack(0, 0, 0, '', leftToRemove, rightToRemove) to begin from index 0 and an empty path.

4. Convert the result set result to a list and return it.

Let’s look at the following illustration to get a better understanding of the solution: