301. Remove Invalid Parentheses

Problem Description

The problem tasks us with correcting a string s that consists of lowercase letters and parentheses. Our goal is to remove the smallest number of parentheses to make the string a valid expression. An expression is considered valid if parentheses are correctly paired and nested. For example, "()()" and "(a)(b)" are valid, but ")(" and "(()" are not. Since there may be multiple ways to remove parentheses and validate the string, we should return a list of all unique valid strings that can result from the minimal number of removals. Order of the output is not important.

Intuition

The solution relies on a Depth-First Search (DFS) approach to generate all possible strings through removing minimum invalid parentheses and test each string for validity. Since we are interested in the least number of removals, there are two important counts: the number of left parentheses that can be removed (l), and the number of right parentheses that can be removed (r). These counts are first determined by iterating through the string and applying simple rules:

1. Increment the left count (l) when we encounter an opening parenthesis.
2. If we encounter a closing parenthesis and there are already opening ones to balance it, we decrement the left count. Otherwise, we increment the right count (r).

With these counts, we use DFS to traverse the string and try the following actions:

• Skip an opening parenthese if we still have left parentheses to remove (l > 0), and proceed to the next character without adding it to our ongoing string t.
• Similarly, skip a closing parenthese if we can still remove right parentheses (r > 0).
• Or, take the current character and add it to t, updating the number of parenthesis added (condition lcnt < rcnt is checking that at any stage in the DFS, we should never have more closing parentheses taken than opening ones).

Every time we reach the end of the string, if both left and right counters are zero, it means we've made valid removals, and we add the ongoing string t to our answers set.

With this recursive approach, all valid combinations of the string s with the minimum necessary removals will be explored and added to the answers set, while invalid paths will be pruned early, optimizing the process. At the end of all DFS calls, the set contains all unique valid strings, which is converted to a list and returned.

Learn more about Breadth-First Search and Backtracking patterns.

Solution Approach

The solution begins by defining a DFS function dfs with the following parameters:

• i: the current index in the string s.
• l: the count of left parentheses that we can still remove.
• r: the count of right parentheses that we can still remove.
• lcnt: the count of left parentheses that have been added to the ongoing string t.
• rcnt: the count of right parentheses that have been added to the ongoing string t.
• t: the current state of the string after removals.

Here are the steps in the implementation:

1. Base Condition: When i equals the length of the string n, it checks if both l and r are zero, indicating that a correct balance has been maintained. If so, it adds the current string t to the set ans.

2. Pruning: The function returns early without further exploring the current branch if:

   • More characters are needed to correct the balance than are remaining in the string (n - i < l + r), or
   • There are more right parentheses than left in t (lcnt < rcnt), breaking the balance rule.

3. Recursion for Removals: The algorithm can choose to skip a parenthesis character if there are still parentheses of that kind left to be removed:

   • For a left parenthesis at the current index (s[i] == '('), if l > 0, the function calls itself recursively without including this character and decrements l.
   • For a right parenthesis (s[i] == ')'), if r > 0, it does the same while decrementing r.

This allows the exploration of all the possibilities where parentheses are excluded from the final string.

4. Recursion for Inclusion: The function also calls itself recursively with the current character included in t:
   • If the current character is a left parenthesis, it increments lcnt.
   • If it's a right parenthesis, it increments rcnt.

This continues the path where the current character is considered part of the valid string.

Before running DFS, we initialize the counts l and r which determine how many of each type of parentheses can be removed, by iterating over s once.

The solution utilizes a set ans to keep track of unique valid strings and a variable n to store the length of the input string s. The set ensures that duplicate solutions are not included providing unique final answers.

After setting initial values for l, r, and n, the DFS function is kicked off and left to explore all valid removal patterns.

After the DFS function has completed its execution, ans will contain all unique strings that can be obtained by removing the minimal amount of parentheses required to make s valid. The last line of the function returns the set as a list. The utilisation of a set is crucial, as it automatically handles the deduplication of valid strings, which is a requirement.

The chosen algorithm and data structures (depth-first search, integers for counters, a string for the current state, and a set for the answers) are all integral to ensuring that the solution is efficient and satisfies the problem's constraints.

Example Walkthrough

Let's use the string s = "(()))(" as an example to illustrate the solution approach.

1. Determining Parentheses to Remove: We begin by iterating through the string s and counting the number of invalid left ( and right ) parentheses.

• Start with l = r = 0.
• For each character in s:
  • If (, increment l to indicate we have another left parenthesis that can be balanced later.
  • If ) and l > 0, it means there's a left parenthesis that can balance it, so we decrement l.
  • If ) and l == 0, there is no left parenthesis to balance it, so we increment r.

2. Setting Up for DFS: After the first iteration, we know we have l = 0 (no extra left parentheses to remove) and r = 2 (there are two unbalanced right parentheses).

3. Running DFS:

• We start at index i = 0 with the initial counts l = 0 and r = 2. Our current string t is empty, and lcnt = rcnt = 0.

• At each step, we make recursive calls considering inclusion or removal of the current parenthesis:

  • When i = 0, s[i] is (. We cannot remove a left parenthesis (l = 0), but we can add it to t. So we add it and make a recursive call with lcnt = 1.
  • At i = 1, we again have (, and proceed similarly, with lcnt now being 2.
  • At i = 2, we encounter ), with lcnt = 2, so we can balance it. We add it to t (recursively continuing with rcnt = 1) and we could also skip it because r > 0. We make two recursive calls, one including it and one excluding it.
  • We continue like this until i equals the length of s.

4. Valid String Condition: Each time we reach the end of s, we check if l and r are both 0. If so, we add t to our set ans. If we took the right path previously, the valid string t becomes "()()".

5. Continuing Search: The DFS continues until all valid combinations of string s with the minimum parentheses removed are explored. Since our example string could have multiple valid answers, the DFS will eventually find and store them all.

6. Collecting Results: When the DFS is done, ans will hold all unique valid strings. If we just removed right parentheses in our example, ans could contain strings like "()()".

The set ans will include every unique solution, which we convert to a list and return.

This approach ensures that all possible strings with the minimum number of parentheses removed are considered without duplicates, thus satisfying the problem's requirement of finding all possible unique valid strings.

Solution Implementation

Time and Space Complexity

The provided code snippet is a Python implementation of an algorithm that removes the minimum number of invalid parentheses to make the input string valid. The algorithm uses Depth-First Search (DFS) with backtracking.

• Time Complexity: Let's denote n as the length of the string s. In the worst case, the DFS will visit every possible combination of parentheses removals. For each character in the input string, the algorithm has up to 3 choices: remove '(', remove ')', or keep the character (if it is a character other than the parenthese) - leading to O(3^n) in the worst case. However, we optimize this complexity by using the l and r counters for the minimum numbers of left and right parentheses that need to be removed, which prunes the recursion tree significantly. Additionally, the lcnt < rcnt condition further prunes invalid states whenever right parentheses count exceed the left parentheses count. Hence, the time complexity is less than O(3^n) but more than O(2^n), making it difficult to pinpoint the exact complexity without a rigorous mathematical derivation. A rough bound could be O(c^n), where c is some constant between 2 and 3.

• Space Complexity: The space complexity is O(n) for the recursion stack since in the worst case, the recursive calls can have a maximum call chain of the length of the string. Furthermore, auxiliary space is needed for the string t in the DFS calls and an extra set ans to store the results, which can have up to O(2^n) combinations (each character is either included or excluded). So, while the stack space is linear in the size of the input, the space required for the solution set can be significant. The total space used is O(n * 2^n), which accounts for the stack space and the generated solutions. However, this is a loose upper bound given that many branches of recursion might be pruned, and not all 2^n combinations will be generated or stored (due to invalid sequences being discarded early).

Learn more about how to find time and space complexity quickly using problem constraints.