301.Remove_Invalid_Parentheses(Hard).md

301. Remove Invalid Parentheses (Hard)

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

Date	Stopwatch	Y/N	Feedback
Jul 8, 2025	28m 36s	Y	First time, watched tutorial but implemented by myself

Edge Cases:

Edge Case 1:

Input: s = "()(("
Output: ["()"]

Walk-through:

We can run DFS with parameters (i, substr, open_cnt, close_cnt), i to keep track of current index of s we are checking, substr is the current substring we have for each DFS call, open_cnt, close_cnt are the number of opening and closing parentheses that we have.

1. Base case, check if i == len(s), which means we have finished checking s, and we check if substr can be added into our ans(). We need to check i. open_cnt == close_cnt, the opening and closing have to match. ii. if substr is longer than current longest, we should update longest, reset ans(), and add this substr into ans(). iii. if len(substr) == longest, we add substr into ans().

2. When substr has not completed, we need to handle s[i]. If s[i] == '(', we can run DFS on the cases that we take this s[i]/'(' and we don't take this '('.

3. If s[i] == ')', we can take it only if open_cnt > close_cnt, when we have more opening at the moment. We also run DFS on the case that we don't take this closing parenthese.

4. Lastly, handle s[i] to take any other English letter, we have to take the letter.

Python:

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # Q: Return a list of unique strings that are valid after min removals
        # S:
        # - Check if index == len(s)
        #   - Compare with current longest substring, if equal, append to res()
        #   - If greater than current longest substring, clear res() and append this one, update longest_substring
        # - Else
        #   - "(": Two cases, we take it or not take it
        #   - ")": 1. Not take it. 2. If open_cnt > close_cnt, take it
        #   - any letter, we should take it
        # TC: O(2^n), n=len(s), SC: O(n)

        longest = -1
        ans = set()
        def dfs(i, substr, open_cnt, close_cnt):
            nonlocal longest, ans
            # Handle substring when it is finished
            if i == len(s):
                if open_cnt == close_cnt:
                    # Compare with previous longest substring
                    if len(substr) > longest:
                        longest = len(substr)
                        ans.clear()
                        ans.add("".join(substr))
                    elif len(substr) == longest:
                        ans.add("".join(substr))
                return
            else:
                # Handle s[i] by symbol
                if s[i] == '(':
                    # Case we take it
                    dfs(i+1, substr + s[i], open_cnt+1, close_cnt)
                    # Case we don't take it
                    dfs(i+1, substr, open_cnt, close_cnt)
                elif s[i] == ')':
                    # Case we take it, iff more opening than closing
                    if open_cnt > close_cnt:
                        dfs(i+1, substr + s[i], open_cnt, close_cnt+1)
                    # Case we don't take it
                    dfs(i+1, substr, open_cnt, close_cnt)
                else:
                    # Take other letter
                    dfs(i+1, substr + s[i], open_cnt, close_cnt)
        dfs(0, "", 0, 0)
        return list(ans)

Time Complexity: $O(2^n)$, each s[i] we can take it or not, and we have n parentheses to try.
Space Complexity: $O(n)$, depth of DFS is at most n, so we can have at most n substrings.