LeetCode 1249: Minimum Remove to Make Valid Parentheses

Brute force

Try all possibilities. For every opening parenthesis we can take it or remove it. For every closing parenthesis, we can remove it or if close count is less than open count, we can take it.

Time: $\mathcal{O}(2^n)$ , space: $\mathcal{O}(n)$ .

class Solution:
    def dfs(self, s, i, curr, open_count, close_count) -> str:
        if i >= len(s):
            return curr if open_count == close_count else ""
        
        if s[i] == "(":
            take_open = self.dfs(s, i+1, curr+s[i], open_count+1, close_count)
            skip_open = self.dfs(s, i+1, curr, open_count, close_count)
            return max(take_open, skip_open, key=len)

        if s[i] == ")":
            take_close = self.dfs(s, i+1, curr+s[i], open_count, close_count+1) if close_count < open_count else ""
            skip_close = self.dfs(s, i+1, curr, open_count, close_count)
            return max(take_close, skip_close, key=len)

        return self.dfs(s, i+1, curr+s[i], open_count, close_count)
        

    def minRemoveToMakeValid(self, s: str) -> str:
        return self.dfs(s, 0, "", 0, 0)

Greedy

With a stack we try to match (or pop) an open as soon as we find a close. At the end, the opens leftover in the stack are extra. If for a close the stack is empty, we consider it as extra. We build the string skipping the extra opens and extra closes.

Without the extra opens and extra closes we have a valid parenthesization. If we take one close from extra_close and add it to our solution, it will not be valid anymore. Likewise, if we add one open from extra_open to our solution, it will not be valid anymore. Only way to have a longer valid solution is to take a pair: an open from extra_open and a close from extra_close. Now, for any open in extra_open, if a close from extra_close came afterwards, we would have popped that open. Therefore the opens in extra_open and closes in extra_close look like: $)\ )\ )\ \cdots \ ) \ (\ \cdots \ ($ .

Time: $\mathcal{O}(n)$ , space: same.

class Solution:        

    def minRemoveToMakeValid(self, s: str) -> str:
        extra_open = []
        extra_close = set()
        for i, c in enumerate(s):
            if c not in "()":
                continue
            if c == "(":
                extra_open.append(i)
                continue
            
            if extra_open:
                extra_open.pop()
            else:
                extra_close.add(i)

        deleted = set(extra_open) | extra_close

        return "".join(c for i, c in enumerate(s) if i not in deleted)

unreasonably effective