Problem statement

https://leetcode.com/problems/remove-invalid-parentheses/

Solution 1

The idea is to use dfs with parematers

  1. ind - current symbol
  2. l - number of ( left to take,
  3. r is number of ) left to take
  4. built is built string so far.

Then we try to built element by element and check that we have good balance. Note, that we can in O(n) understand how many open and closing brackets we need: we need to iterate through our string and if we meet (, increase lft by one and if we se closing bracket and balance is zero, we do not do anything, if we have closing bracket and balance is positive, subtact one. What we have as total now in code is number of open and closed brackets we need to keep.

Note also that there is optimization if we use not l and r, but four parameters instead: number of brackets taken already and number of brackets need to be removed: in this way some of the options will be cut earlier: if we can not finish to built string, no need to continue.

Complexity

It is potentially O(2^n), where n is length of string.

Code

class Solution:
    def removeInvalidParentheses(self, s):
        lft = 0
        for char in s:
            if char == "(" : lft += 1
            if char == ")" : lft -= (lft > 0)
                
        total = s.count("(") - lft
        ans = set()
        
        def dfs(ind, l, r, built):
            if ind == len(s) and l == 0 and r == 0:
                ans.add(built)
            if ind == len(s): return
            
            if s[ind] == "(":
                if l > 0: dfs(ind + 1, l - 1, r, built + s[ind])
                dfs(ind + 1, l, r, built)
            elif s[ind] == ")":
                if r > 0 and l <= r - 1: dfs(ind + 1, l, r - 1, built + s[ind])
                dfs(ind + 1, l, r, built)
            else:
                dfs(ind + 1, l, r, built + s[ind])
                
        dfs(0, total, total, "")
        return ans

Solution 2

Let dp(i, bal) will return all solutions, which created from string (i -> end) and having balance of open and closing brackets equal to bal.

  1. If we reached the end of the string and balance is zero, we return "" solution.
  2. If balance is negative or we reached the end of string, there is no solution possible with this situation, no matter what was before.
  3. Then, we need to consider two options: first one when we add new symbol, then we update solution as s[i] + suff for every suffix suff in dp(i + 1, bal1), where bal1 is new balance.
  4. Second is when we do not take symbol, we can do it only if we have bracket ( or ), not letter. We add it to our answer as well.
  5. Finally, we evaluate dp(0, 0) and choose all elements with maximum length.

Complexity

It is still O(2^n)

Code

class Solution:
    def removeInvalidParentheses(self, s):
        @lru_cache(None)
        def dp(i, bal): 
            if i == len(s) and bal == 0: return set([""])
            if bal < 0 or i == len(s): return set()
            bal1 = bal + (s[i] == "(") - (s[i] == ")")
            ans = set(s[i] + suff for suff in dp(i + 1, bal1))
            if s[i] in '()': ans |= dp(i + 1, bal)
            return ans

        valid = dp(0, 0)
        maxLen = max(valid, key = len)
        return [x for x in valid if len(x) == len(maxLen)]