# Remove Invalid Parentheses **Difficulty:** HARD [External](https://leetcode.com/problems/remove-invalid-parentheses) Canonical: https://scaleengineer.com/dsa/problems/remove-invalid-parentheses **Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking) **Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** String **Companies:** [Google](https://scaleengineer.com/companies/google), [Snowflake](https://scaleengineer.com/companies/snowflake), [Rubrik](https://scaleengineer.com/companies/rubrik), [Deliveroo](https://scaleengineer.com/companies/deliveroo) --- ## Problem Given a string `s` that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return _a list of **unique strings** that are valid with the minimum number of removals_. You may return the answer in **any order**. **Example 1:** **Input:** s = "()())()" **Output:** ["(())()","()()()"] **Example 2:** **Input:** s = "(a)())()" **Output:** ["(a())()","(a)()()"] **Example 3:** **Input:** s = ")(" **Output:** [""] **Constraints:** * `1 <= s.length <= 25` * `s` consists of lowercase English letters and parentheses `'('` and `')'`. * There will be at most `20` parentheses in `s`. # Approaches ## Brute Force - Generate All Subsequences This approach generates all possible subsequences of the input string by either including or excluding each character. For each subsequence, we check if it forms a valid parentheses string. Among all valid strings, we keep only those with the maximum length (minimum removals). **Time:** O(2^n * n) where n is the length of string. We generate 2^n subsequences and each validation takes O(n) time · **Space:** O(2^n * n) for storing all possible subsequences and the recursion stack **Pros:** Simple and straightforward approach; Guaranteed to find all possible solutions; Easy to understand and implement **Cons:** Extremely inefficient for larger inputs; Generates many unnecessary subsequences; High memory usage due to storing all subsequences ### Explanation The brute force approach uses recursion to generate all possible subsequences of the input string. At each position, we have two choices: include the current character or exclude it. We recursively explore both possibilities and collect all valid parentheses strings. Finally, we filter the results to keep only those with minimum removals. ```java public List removeInvalidParentheses(String s) { Set result = new HashSet<>(); generateSubsequences(s, 0, "", result); // Find maximum length among valid strings int maxLen = 0; for (String str : result) { maxLen = Math.max(maxLen, str.length()); } // Keep only strings with maximum length List finalResult = new ArrayList<>(); for (String str : result) { if (str.length() == maxLen) { finalResult.add(str); } } return finalResult; } private void generateSubsequences(String s, int index, String current, Set result) { if (index == s.length()) { if (isValid(current)) { result.add(current); } return; } // Include current character generateSubsequences(s, index + 1, current + s.charAt(index), result); // Exclude current character generateSubsequences(s, index + 1, current, result); } private boolean isValid(String s) { int count = 0; for (char c : s.toCharArray()) { if (c == '(') count++; else if (c == ')') { count--; if (count < 0) return false; } } return count == 0; } ``` ### Algorithm 1. Use recursion to generate all possible subsequences 2. At each position, try both including and excluding the character 3. Check if each generated subsequence is a valid parentheses string 4. Among all valid strings, keep only those with maximum length 5. Return the result as a list ## DFS with Pruning This approach uses depth-first search with intelligent pruning to avoid generating invalid subsequences. We calculate the minimum number of left and right parentheses to remove beforehand, then use DFS to explore only promising paths. **Time:** O(2^(l+r)) where l and r are the number of left and right parentheses to remove. In worst case, this is still exponential but much better than brute force · **Space:** O((l+r) * n) for the recursion stack and storing results **Pros:** More efficient than brute force due to pruning; Avoids generating many invalid subsequences; Still guarantees finding all optimal solutions **Cons:** Still exponential time complexity in worst case; Can generate duplicate results that need to be handled; Complex implementation with multiple conditions ### Explanation We first scan the string to determine how many left and right parentheses need to be removed. Then we use DFS to try removing parentheses while maintaining the constraint that we don't remove more than necessary. We also use pruning to avoid exploring paths that cannot lead to valid solutions. ```java public List removeInvalidParentheses(String s) { List result = new ArrayList<>(); // Calculate minimum removals needed int leftRem = 0, rightRem = 0; for (char c : s.toCharArray()) { if (c == '(') { leftRem++; } else if (c == ')') { if (leftRem > 0) { leftRem--; } else { rightRem++; } } } dfs(s, 0, leftRem, rightRem, 0, "", result); return result; } private void dfs(String s, int index, int leftRem, int rightRem, int open, String path, List result) { if (index == s.length()) { if (leftRem == 0 && rightRem == 0 && open == 0) { result.add(path); } return; } char c = s.charAt(index); // Try removing current character if it's a parenthesis if ((c == '(' && leftRem > 0) || (c == ')' && rightRem > 0)) { dfs(s, index + 1, leftRem - (c == '(' ? 1 : 0), rightRem - (c == ')' ? 1 : 0), open, path, result); } // Try keeping current character if (c != '(' && c != ')') { dfs(s, index + 1, leftRem, rightRem, open, path + c, result); } else if (c == '(') { dfs(s, index + 1, leftRem, rightRem, open + 1, path + c, result); } else if (c == ')' && open > 0) { dfs(s, index + 1, leftRem, rightRem, open - 1, path + c, result); } } ``` ### Algorithm 1. Calculate minimum number of left and right parentheses to remove 2. Use DFS to explore all possible ways to remove exactly that many parentheses 3. At each step, try both removing and keeping the current character 4. Use pruning to avoid invalid paths (e.g., more closing than opening brackets) 5. Collect all valid results when we reach the end of string ## BFS Level-by-Level Exploration This approach uses breadth-first search to explore all possible strings level by level, where each level represents removing one more character. We stop as soon as we find valid strings, ensuring minimum removals. **Time:** O(2^n) in worst case, but typically much better as it stops early when valid strings are found · **Space:** O(2^n) for the queue and visited set in worst case **Pros:** Guarantees minimum number of removals due to level-by-level exploration; Stops as soon as valid solutions are found; Handles duplicates effectively with visited set; More intuitive approach than DFS **Cons:** Can use significant memory for the queue and visited set; Still exponential in worst case scenarios; May generate many intermediate invalid strings ### Explanation We use BFS to systematically explore all possible strings by removing characters one by one. We start with the original string and generate all possible strings by removing one character. If we find valid strings at any level, we stop there since BFS guarantees we found the minimum number of removals. We use a set to avoid processing duplicate strings. ```java public List removeInvalidParentheses(String s) { List result = new ArrayList<>(); if (s == null) return result; Queue queue = new LinkedList<>(); Set visited = new HashSet<>(); queue.offer(s); visited.add(s); boolean found = false; while (!queue.isEmpty() && !found) { int size = queue.size(); for (int i = 0; i < size; i++) { String current = queue.poll(); if (isValid(current)) { result.add(current); found = true; } if (!found) { // Generate all possible strings by removing one character for (int j = 0; j < current.length(); j++) { // Only remove parentheses if (current.charAt(j) != '(' && current.charAt(j) != ')') { continue; } String next = current.substring(0, j) + current.substring(j + 1); if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } } } } return result; } private boolean isValid(String s) { int count = 0; for (char c : s.toCharArray()) { if (c == '(') { count++; } else if (c == ')') { count--; if (count < 0) return false; } } return count == 0; } ``` ### Algorithm 1. Initialize BFS queue with the original string 2. For each level, process all strings in the queue 3. Check if any string is valid - if found, add to result and stop 4. If no valid string found, generate all possible strings by removing one parenthesis 5. Add new strings to queue if not visited before 6. Continue until valid strings are found # Solutions ### Java ```java import java.util.ArrayList ; import java.util.HashSet ; import java.util.List ; import java.util.Set ; public class Remove_Invalid_Parentheses { // reference: https://leetcode.com/problems/remove-invalid-parentheses/solution/ class Solution_dfs { private Set < String > validExpressions = new HashSet < String >(); private int minimumRemoved ; private void reset () { this . validExpressions . clear (); this . minimumRemoved = Integer . MAX_VALUE ; } private void dfs ( String s , int index , int leftCount , int rightCount , StringBuilder expression , int removedCount ) { // If we have reached the end of string. if ( index == s . length ()) { // If the current expression is valid. if ( leftCount == rightCount ) { // If the current count of removed parentheses is <= the current minimum count if ( removedCount <= this . minimumRemoved ) { // Convert StringBuilder to a String. This is an expensive operation. // So we only perform this when needed. String possibleAnswer = expression . toString (); // If the current count beats the overall minimum we have till now if ( removedCount < this . minimumRemoved ) { this . validExpressions . clear (); this . minimumRemoved = removedCount ; } this . validExpressions . add ( possibleAnswer ); } } } else { char currentCharacter = s . charAt ( index ); int length = expression . length (); // If the current character is neither an opening bracket nor a closing one, // simply recurse further by adding it to the expression StringBuilder if ( currentCharacter != '(' && currentCharacter != ')' ) { expression . append ( currentCharacter ); this . dfs ( s , index + 1 , leftCount , rightCount , expression , removedCount ); expression . deleteCharAt ( length ); } else { // Recursion where we delete the current character at 'index' and move forward to 'index+1' this . dfs ( s , index + 1 , leftCount , rightCount , expression , removedCount + 1 ); expression . append ( currentCharacter ); // If it's an opening parenthesis, consider it and recurse if ( currentCharacter == '(' ) { this . dfs ( s , index + 1 , leftCount + 1 , rightCount , expression , removedCount ); } else if ( rightCount < leftCount ) { // For a closing parenthesis, only recurse if right < left this . dfs ( s , index + 1 , leftCount , rightCount + 1 , expression , removedCount ); } // Undoing the append operation for other recursions. expression . deleteCharAt ( length ); } } } public List < String > removeInvalidParentheses ( String s ) { this . reset (); this . dfs ( s , 0 , 0 , 0 , new StringBuilder (), 0 ); return new ArrayList ( this . validExpressions ); } } public class Solution_bfs { public List < String > removeInvalidParentheses ( String s ) { List < String > res = new ArrayList <>(); // sanity check if ( s == null ) return res ; Set < String > visited = new HashSet <>(); Queue < String > queue = new LinkedList <>(); // initialize queue . add ( s ); visited . add ( s ); boolean found = false ; while (! queue . isEmpty ()) { s = queue . poll (); if ( isValid ( s )) { // found an answer, add to the result res . add ( s ); found = true ; } if ( found ) continue ; // continue to check all in queue, but no more new adding to queue // generate all possible states for ( int i = 0 ; i < s . length (); i ++) { // we only try to remove left or right parent if ( s . charAt ( i ) != '(' && s . charAt ( i ) != ')' ) continue ; String t = s . substring ( 0 , i ) + s . substring ( i + 1 ); // skip char at index=i if (! visited . contains ( t )) { // for each state, if it's not visited, add it to the queue queue . add ( t ); visited . add ( t ); } } } return res ; } // helper function checks if string s contains valid parantheses boolean isValid ( String s ) { int count = 0 ; for ( int i = 0 ; i < s . length (); i ++) { char c = s . charAt ( i ); if ( c == '(' ) count ++; if ( c == ')' ) count --; if ( count < 0 ) return false ; } return count == 0 ; } } } ############ class Solution { private String s ; private int n ; private Set < String > ans = new HashSet <>(); public List < String > removeInvalidParentheses ( String s ) { this . s = s ; this . n = s . length (); int l = 0 , r = 0 ; for ( char c : s . toCharArray ()) { if ( c == '(' ) { ++ l ; } else if ( c == ')' ) { if ( l > 0 ) { -- l ; } else { ++ r ; } } } dfs ( 0 , l , r , 0 , 0 , "" ); return new ArrayList <>( ans ); } private void dfs ( int i , int l , int r , int lcnt , int rcnt , String t ) { if ( i == n ) { if ( l == 0 && r == 0 ) { ans . add ( t ); } return ; } if ( n - i < l + r || lcnt < rcnt ) { return ; } char c = s . charAt ( i ); if ( c == '(' && l > 0 ) { dfs ( i + 1 , l - 1 , r , lcnt , rcnt , t ); } if ( c == ')' && r > 0 ) { dfs ( i + 1 , l , r - 1 , lcnt , rcnt , t ); } int x = c == '(' ? 1 : 0 ; int y = c == ')' ? 1 : 0 ; dfs ( i + 1 , l , r , lcnt + x , rcnt + y , t + c ); } } ``` ### Python ```python # python3 class Solution : ''' - `i` 表示当前处理到字符串 $s$ 的第 $i$ 个字符； - `l` 和 `r` 分别表示剩余待删除的左、右括号的数量； - `t` 表示当前得到的字符串； - `lcnt` 和 `rcnt` 分别表示当前得到的字符串中左、右括号的数量。 ''' def removeInvalidParentheses ( self , s : str ) -> List [ str ]: def dfs ( i , l , r , lcnt , rcnt , t ): if i == n : if l == 0 and r == 0 : ans . add ( t ) return if n - i < l + r or lcnt < rcnt : return if s [ i ] == '(' and l : dfs ( i + 1 , l - 1 , r , lcnt , rcnt , t ) # note here is elif, not another if, because, to get min-deletion valid string, always delete from extra '(' first elif s [ i ] == ')' and r : dfs ( i + 1 , l , r - 1 , lcnt , rcnt , t ) # s[i] is a char, or not delete any '(' or ')' so wait for future recursions to do it dfs ( i + 1 , l , r , lcnt + ( s [ i ] == '(' ), rcnt + ( s [ i ] == ')' ), t + s [ i ]) l = r = 0 for c in s : # count how many ( or ) to be removed to get valid one if c == '(' : l += 1 elif c == ')' : if l : l -= 1 else : r += 1 ans = set () n = len ( s ) dfs ( 0 , l , r , 0 , 0 , '' ) # minimum removal, is archieved by strictly applying counted l/r return list ( ans ) # bfs version class Solution ( object ): def removeInvalidParentheses ( self , s ): def isvalid ( s ): ctr = 0 for c in s : if c == '(' : ctr += 1 elif c == ')' : ctr -= 1 if ctr < 0 : return False return ctr == 0 ''' >>> a = {1,2,3,1,2,3} >>> a {1, 2, 3} >>> list(a) [1, 2, 3] ''' level = { s } while True : valid = filter ( isvalid , level ) if valid : return valid level = { s [: i ] + s [ i + 1 :] for s in level for i in range ( len ( s ))} # bfs version, python3 class Solution : def removeInvalidParentheses ( self , s : str ) -> List [ str ]: def isvalid ( s ): ctr = 0 for c in s : if c == '(' : ctr += 1 elif c == ')' : ctr -= 1 if ctr < 0 : return False return ctr == 0 level = { s } while True : valid = filter ( isvalid , level ) converted = list ( valid ) if converted : # in python3, valid from filter() will always be not-None, so need to convert to list return converted level = { s [: i ] + s [ i + 1 :] for s in level for i in range ( len ( s ))} # official-solution: Backtracking. https://leetcode.com/problems/remove-invalid-parentheses/editorial/ class Solution ( object ): def __init__ ( self ): self . valid_expressions = None self . min_removed = None def reset ( self ): self . valid_expressions = set () self . min_removed = float ( "inf" ) """ string: The original string we are recursing on. index: current index in the original string. left: number of left parentheses till now. right: number of right parentheses till now. ans: the resulting expression in this particular recursion. ignored: number of parentheses ignored in this particular recursion. """ def remaining ( self , string , index , left_count , right_count , expr , rem_count ): # If we have reached the end of string. if index == len ( string ): # If the current expression is valid. The only scenario where it can be # invalid here is if left > right. The other way around we handled early on in the recursion. if left_count == right_count : if rem_count <= self . min_removed : # This is the resulting expression. # Strings are immutable in Python so we move around a list in the recursion # and eventually join to get the final string. possible_ans = "" . join ( expr ) # If the current count of brackets removed < current minimum, ignore # previous answers and update the current minimum count. if rem_count < self . min_removed : self . valid_expressions = set () self . min_removed = rem_count self . valid_expressions . add ( possible_ans ) else : current_char = string [ index ] # If the current character is not a parenthesis, just recurse one step ahead. if current_char != '(' and current_char != ')' : expr . append ( current_char ) self . remaining ( string , index + 1 , left_count , right_count , expr , rem_count ) expr . pop () else : # Else, one recursion is with ignoring the current character. # So, we increment the ignored counter and leave the left and right untouched. self . remaining ( string , index + 1 , left_count , right_count , expr , rem_count + 1 ) expr . append ( current_char ) # If the current parenthesis is an opening bracket, we consider it # and increment left and move forward if string [ index ] == '(' : self . remaining ( string , index + 1 , left_count + 1 , right_count , expr , rem_count ) elif right_count < left_count : # If the current parenthesis is a closing bracket, we consider it only if we # have more number of opening brackets and increment right and move forward. self . remaining ( string , index + 1 , left_count , right_count + 1 , expr , rem_count ) expr . pop () def removeInvalidParentheses ( self , s ): """ :type s: str :rtype: List[str] """ # Reset the class level variables that we use for every test case. self . reset () # Recursive call self . remaining ( s , 0 , 0 , 0 , [], 0 ) return list ( self . valid_expressions ) # official-solution: Limited Backtracking. https://leetcode.com/problems/remove-invalid-parentheses/editorial/ class Solution : def removeInvalidParentheses ( self , s ): """ :type s: str :rtype: List[str] """ left = 0 right = 0 # First, we find out the number of misplaced left and right parentheses. for char in s : # Simply record the left one. if char == '(' : left += 1 elif char == ')' : # If we don't have a matching left, then this is a misplaced right, record it. right = right + 1 if left == 0 else right # Decrement count of left parentheses because we have found a right # which CAN be a matching one for a left. left = left - 1 if left > 0 else left result = {} def recurse ( s , index , left_count , right_count , left_rem , right_rem , expr ): # If we reached the end of the string, just check if the resulting expression is # valid or not and also if we have removed the total number of left and right # parentheses that we should have removed. if index == len ( s ): if left_rem == 0 and right_rem == 0 : ans = "" . join ( expr ) result [ ans ] = 1 else : # The discard case. Note that here we have our pruning condition. # We don't recurse if the remaining count for that parenthesis is == 0. if ( s [ index ] == '(' and left_rem > 0 ) or ( s [ index ] == ')' and right_rem > 0 ): recurse ( s , index + 1 , left_count , right_count , left_rem - ( s [ index ] == '(' ), right_rem - ( s [ index ] == ')' ), expr ) expr . append ( s [ index ]) # Simply recurse one step further if the current character is not a parenthesis. if s [ index ] != '(' and s [ index ] != ')' : recurse ( s , index + 1 , left_count , right_count , left_rem , right_rem , expr ) elif s [ index ] == '(' : # Consider an opening bracket. recurse ( s , index + 1 , left_count + 1 , right_count , left_rem , right_rem , expr ) elif s [ index ] == ')' and left_count > right_count : # Consider a closing bracket. recurse ( s , index + 1 , left_count , right_count + 1 , left_rem , right_rem , expr ) # Pop for backtracking. expr . pop () # Now, the left and right variables tell us the number of misplaced left and # right parentheses and that greatly helps pruning the recursion. recurse ( s , 0 , 0 , 0 , left , right , []) return list ( result . keys ()) ############ class Solution ( object ): def removeInvalidParentheses ( self , s ): """ :type s: str :rtype: List[str] """ def isValid ( s ): stack = [] for c in s : if c == "(" : stack . append ( "(" ) elif c == ")" : stack . append ( ")" ) if len ( stack ) >= 2 and stack [ - 2 ] + stack [ - 1 ] == "()" : stack . pop () stack . pop () return len ( stack ) def dfs ( s , res , cache , length ): if s in cache : return if len ( s ) == length : if isValid ( s ) == 0 : res . append ( s ) return for i in range ( 0 , len ( s )): if s [ i ] == "(" or s [ i ] == ")" and len ( s ) - 1 >= length : dfs ( s [: i ] + s [ i + 1 :], res , cache , length ) cache . add ( s [: i ] + s [ i + 1 :]) prepLeft = "" for i in range ( 0 , len ( s )): if s [ i ] == "(" : prepLeft += s [ i :] break elif s [ i ] != ")" : prepLeft += s [ i ] prepRight = "" for i in reversed ( range ( 0 , len ( prepLeft ))): if prepLeft [ i ] == ")" : prepRight += prepLeft [: i + 1 ][:: - 1 ] break elif prepLeft [ i ] != "(" : prepRight += prepLeft [ i ] s = prepRight [:: - 1 ] length = len ( s ) - isValid ( s ) res = [] cache = set () dfs ( s , res , cache , length ) return res ``` ### CPP ```cpp // OJ: https://leetcode.com/problems/remove-invalid-parentheses/ // Time: O(2^N) // Space: O(N) class Solution { public: vector < string > removeInvalidParentheses ( string s ) { int N = s . size (); vector < int > right ( N + 1 ); for ( int i = N - 1 ; i >= 0 ; -- i ) right [ i ] = max ( 0 , right [ i + 1 ] + ( s [ i ] == '(' || s [ i ] == ')' ? ( s [ i ] == ')' ? 1 : - 1 ) : 0 )); unordered_set < string > ans ; string tmp ; function < void ( int , int ) > dfs = [ & ]( int i , int left ) { if ( i == N ) { if ( left == 0 ) ans . insert ( tmp ); return ; } if ( s [ i ] == '(' ) { if ( left + 1 > right [ i + 1 ]) { // we can remove this '(' dfs ( i + 1 , left ); } ++ left ; } else if ( s [ i ] == ')' ) { if ( right [ i ] > left ) { // we can remove this ')' dfs ( i + 1 , left ); } if ( left > 0 ) { -- left ; } else return ; } tmp . push_back ( s [ i ]); dfs ( i + 1 , left ); tmp . pop_back (); }; dfs ( 0 , 0 ); return vector < string > ( begin ( ans ), end ( ans )); } }; ```