LC 0301 [H] Remove Invalid Parentheses - ALawliet/algorithms GitHub Wiki

prereq: minimum remove to make valid parens

  • check valid by counting parens
  • BFS backtracking to generate next level that consists of nodes with a parens removed with a set to prevent duplicates
  • return the answer when we find any level that has a valid node (cause it is the highest level = minimum to remove, that level will also contain the rest of the valid nodes with the same length (can't be shorter strings than that) that we need to check)

Regarding the time complexity, I think one way we can think about the search space is as a power subset of the original string. So it includes all possible substrings from 0 character to N(number of chars in the input string) characters. So the possibilities are 2^n. (we either pick a character or don't pick it) For each subset we check if it is a valid string so it becomes n*(2^n)

if (found) continue; this ensures once we've found a valid parentheses pattern, we don't do any further bfs using items pending in the queue since any further bfs would only yield strings of smaller length. However the items already in queue need to be processed since there could be other solutions of the same length. great solution.

All items will be processed that are already enqueued. However no new levels would be added because - if(found), will not allow code execution to go ahead (instead - continue, sends it back to while((!queue.isEmpty())). And this is sufficient, because question asks us to find valid strings after minimum deletions. Had the question been find all possible valid strings after any deletions -- then we don't need if(found) condition.

great explanation. This 'continue' really helps terminate the BFS early but still allow you to process all valid patterns of same length. Also one important thing why this works is because once you have a string of length k that is valid, all those strings in the next level which have a length of k - 1 are definitely not valid (you need to remove a pair to make it valid again). Notice some next level k - 1 length strings can be added to the queue if a valid pattern comes late in the current level and found only becomes true it encounters the first valid string. And once found is true, all the strings remaining in the queue will still be processed and checked if valid except no children will be added to the queue.

Also questions asks for Min removal of Brackets, if you have found a valid string , processing it further will not give the Valid String with Minimum no of Brackets Removal.

@SenyangZ Hi, there is no such problem with this code. It actually generates only ["()()"] on the given input "()(()". You may find it weird since the code does not explicitly record the maximum length of the valid parentheses.

However, it does it implicitly. For a string of parentheses to be valid, its number of parentheses should be even. And at any time, strings in queue will only differ in length of 1 (this is the implicit control). When we find "()()" to be valid, both "()" and "" have not been added to queue yet and all the shorter strings are of length of 3, which must be invalid.

utayao 29 February 12, 2019 11:12 AM

Read More I think the key point is the bool variable "found". Once a string is found to be valid in a level, the variable "found" will be set to true. That means only other strings in the same level will be checked and no shorter strings will be generated for the next level.

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def valid(s):
            l = 0
            r = 0
            for p in s:
                if p == '(':
                    l += 1
                elif p == ')':
                    if l:
                        l -= 1
                    else:
                        r += 1
            return l + r == 0

        Q = deque( [s] )
        visited = set( [s] )
                
        while Q:
            level = [] # we only have to use the first valid level

            for _ in range(len(Q)):
                s = Q.popleft()
                
                if valid(s): # queue contains the highest = minimum level that is valid
                    level.append(s)
                else:
                    for i in range(len(s)):
                        prefix, suffix = s[:i], s[i+1:]
                        rest = prefix + suffix # exclude 1 char a time
                        if rest not in visited:
                            Q.append(rest)
                            visited.add(rest)
                            
            if level: return level # we only have to use the first valid level because the following levels are no longer the minimum
class Solution:
    def removeInvalidParentheses(self, s):
        res = []

        Q = deque([s])
        visited = set([s])
        
        while Q:            
            valid_level = False

            for _ in range(len(Q)):
                s = Q.popleft() # node
                
                # if any s valid in this level so far (keep in mind it doesn't have to be the first s)
                # we have found the level with the min parens => just process rest of this level and done (because next level is even less parens)
                if isValid(s):
                    valid_level = True
                    res.append(s)
                    
                # but if not valid level => queue the next level with the rest
                if not valid_level:
                    for i in range(len(s)):
                        prefix, suffix = s[:i], s[i+1:]
                        rest = prefix + suffix
                        if rest not in visited:
                            visited.add(rest)
                            Q.append(rest) 
            
            # make sure not to process the next level if we already processed the level with the min parens
            if valid_level: break

        return res
class Solution:
    def removeInvalidParentheses(self, s):
        valids = []
        levelQ = set([s])
        
        while not valids:
            for s in levelQ:
                if isValid(s):
                    valids.append(s)
                    
            if valids: return valids
            
            nextLevelQ = set()
            for s in levelQ:
                for i in range(len(s)):
                    prefix = s[:i]
                    suffix = s[i+1:]
                    rest = prefix + suffix
                    nextLevelQ.add(rest)
            levelQ = nextLevelQ

Great idea! I think it is more clear if you can process all candidate strings with same length at one time.

public class Solution {
    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()) { // in queue
        int size = queue.size();

        for (int i = 0; i < size; i++) { // range across the level
            String cur = queue.remove();

            // Valid
            if (isValid(cur)) {
                found = true;
                res.add(cur);
            }

            // Not Valid Then Delete 
            if (!found) {
                for (int j = 0; j < cur.length(); j++) {
                    if (cur.charAt(j) != '(' && cur.charAt(j) != ')') continue;
                    String newStr = cur.substring(0, j) + cur.substring(j + 1); // rest = prefix + suffix
                    if (!visited.contains(newStr)) {
                        queue.add(newStr);
                        visited.add(newStr);
                    }
                }
            }
        }

        if (found) break; // skip the rest of the queue, which is the next level, and must be invalid because it is odd (you need to remove a pair to make it valid)
    }
      
      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-- == 0) return false;
      }
    
      return count == 0;
    }
}
# T: O(n * 2^n)
class Solution:
    def removeInvalidParentheses(self, s):
        def isValid(s):
            count = 0
            for p in s:
                if p == '(':
                    count += 1
                elif p == ')':
                    count -= 1
                if count < 0: return False
            return count == 0

        valid = []
        Q = {s} # level
        while not valid:
            valid = list(filter(isValid, Q))
            if valid: return valid
            Q = {s[:i] + s[i+1:] for s in Q for i in range(len(s))} # next level if we removed 1
class Solution:
    def removeInvalidParentheses(self, s):
        def isValid(s):
            count = 0
            for p in s:
                if p == '(':
                    count += 1
                elif p == ')':
                    count -= 1
                    if count < 0: return False
            return count == 0

        valid = []
        level = {s}
        while not valid:
            for s in level:
                if isValid(s):
                    valid.append(s)
            if valid: return valid
            nextlevel = set()
            for s in level:
                for i in range(len(s)):
                    nextlevel.add(s[:i] + s[i+1:])
            level = nextlevel

footer

⚠️ **GitHub.com Fallback** ⚠️