Minimum Remove to Make Valid Parentheses | Medium

Date Time 1 min Tags Facebook

Leetcode

Intuition:

  • Calculate the invariant (out of place) parentheses first and then remove them.

Gotchas:

  • Unlike getting all possibilities, this doesn't require recursion / search / stack or queue.
  • Trying to solve by looping in sequence doesn't work. Right parentheses can be removed in sequence, but Left parentheses are efficiently removed in reverse.
  • Character can be set to "" instead of creating a new string

Base cases:

  • None for loops.
  • Splitting the string into a char list makes it easier to "remove" a character

Solution:

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:

        left_rem = 0
        s = [c for c in s ]
        N = len(s)
        for i in range(N):
            if s[i] == '(':
                left_rem +=1       
            elif s[i] == ')':
                if left_rem > 0:
                    left_rem -= 1
                else:
                    s[i] = ''

        i = N-1
        while left_rem and i > -1:
            if s[i] == '(':
                s[i] = ''
                left_rem -=1
            i -= 1

        return "".join(s)

Complexity Analysis:

O(N)

Comments

comments powered by Disqus