LeetCode 301: Remove Invalid Parentheses Solution in Python – A Step-by-Step Guide

What Is LeetCode 301: Remove Invalid Parentheses?

In LeetCode 301: Remove Invalid Parentheses, you’re given a string s containing parentheses and letters (e.g., "()())()"), and your task is to remove the minimum number of parentheses to make it valid—where every open parenthesis "(" has a matching close parenthesis ")". You need to return all possible valid strings after those minimal removals. For example, "()())()" can become ["()()()", "(())()"] by removing one parenthesis each way. This problem tests your ability to explore string modifications, sharing a vibe with LeetCode 20: Valid Parentheses but with a twist of finding all solutions.

Problem Statement

• Input: A string s with parentheses and letters.
• Output: A list of strings—all possible valid results after minimum removals.
• Rules: Remove least number of parentheses; return all valid possibilities; order doesn’t matter.

Constraints

• s length: 1 to 25.
• Characters: lowercase English letters, "(", ")".
• At least one valid result exists.

Examples

• Input: s = "()())()"
• Output: ["()()()", "(())()"]
• Input: s = "(a)())()"
• Output: ["(a)()()", "(a())()"]
• Input: s = ")("
• Output: [""]

Understanding the Problem: Fixing the Balance

To solve LeetCode 301: Remove Invalid Parentheses in Python, we need to take a string like "()())()", figure out how many extra "(" or ")" make it invalid, remove the smallest number possible, and list every way to get a valid string. For "()())()", there’s one extra ")" (count "(" = 3, ")" = 4), so we remove one ")" in different spots to get ["()()()", "(())()"]. Trying every removal combo could work but would be slow, so we’ll use smarter approaches:

• Best Solution (BFS with Pruning): O(2^n) time optimized, O(n) space—fast and broad.
• Alternative Solution (DFS with Backtracking): O(2^n) time, O(n) space—recursive and clear.

Let’s dive into the BFS solution with a friendly breakdown that’s easy to follow.

Best Solution: BFS with Pruning

Why This Is the Best Solution

The BFS with pruning approach is the top choice for LeetCode 301 because it’s efficient—O(2^n) time reduced by pruning invalid paths early—and uses O(n) space for the queue. It explores level-by-level, starting with minimal removals, and stops once it finds valid strings, ensuring the least removals. It’s like searching a maze floor-by-floor, stopping when you find the exits—perfect for getting all minimal solutions fast!

How It Works

Let’s imagine this like cleaning up a messy room:

• Step 1: Count Mismatches:
• Scan the string to count extra "(" (left) and ")" (right) that need removal.
• Use a counter: +1 for "(", -1 for ")", track when it goes negative (extra ")").
• Step 2: BFS Exploration:
• Start with the original string and counts of left/right to remove.
• Queue: (string, index, left, right).
• For each string, try removing one parenthesis at a time, level-by-level.
• Step 3: Prune and Validate:
• Only keep strings that could still be valid (check balance as you go).
• Stop at the first level with valid strings—minimal removals guaranteed.
• Step 4: Why It Works:
• BFS ensures we hit minimal removals first (level order).
• Pruning skips dead-end paths, speeding it up.
• Set avoids duplicates.

It’s like tidying up step-by-step—find the quickest fixes first!

Step-by-Step Example

Example: s = "()())()"

• Step 1: Count Mismatches:
• Counter: ( → +1 = 1, ) → -1 = 0, ( → +1 = 1, ) → -1 = 0, ) → -1 = -1 (extra ")"), ( → +1 = 0, ) → -1 = -1 (extra ")").
• left = 0, right = 1 (one extra ")").
• Step 2: BFS:
• Queue: [(()())(), 0, 0, 1)], seen = set(), result = [].
• Level 0 (remove 0):
• "()())()", idx=0: Skip "(", next idx=1.
• "()())()", idx=1: Remove ")", "()()()", check: valid! Add to result, seen = {"()()()"}.
• Stop here (valid found).
• Level 1 (remove 1):
• From "()())()", try removing others:
• Remove ")" at 4: "(())()", valid, seen = {"()()()", "(())()"}.
• Result: ["()()()", "(())()"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codefrom collections import deque

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # Step 1: Count extra parentheses
        left = right = 0
        for char in s:
            if char == '(':
                left += 1
            elif char == ')':
                if left > 0:
                    left -= 1  # Pair with an open
                else:
                    right += 1  # Extra close

        # Step 2: BFS setup
        queue = deque([(s, 0, left, right)])  # (string, index, left, right)
        seen = set([s])  # Track seen strings
        result = []
        found = False

        # Step 3: BFS loop
        while queue and not found:
            level_size = len(queue)
            for _ in range(level_size):
                curr_s, idx, l, r = queue.popleft()

                # Step 4: Check if valid
                if l == 0 and r == 0 and self.is_valid(curr_s):
                    result.append(curr_s)
                    found = True  # Stop at this level
                # Step 5: Try removing at idx
                elif idx < len(curr_s):
                    # Keep current char
                    queue.append((curr_s, idx + 1, l, r))
                    # Remove char if parenthesis
                    if curr_s[idx] == '(' and l > 0:
                        new_s = curr_s[:idx] + curr_s[idx + 1:]
                        if new_s not in seen:
                            seen.add(new_s)
                            queue.append((new_s, idx, l - 1, r))
                    elif curr_s[idx] == ')' and r > 0:
                        new_s = curr_s[:idx] + curr_s[idx + 1:]
                        if new_s not in seen:
                            seen.add(new_s)
                            queue.append((new_s, idx, l, r - 1))

        return result

    # Helper to check if string is valid
    def is_valid(self, s):
        count = 0
        for char in s:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0

• Line 6-14: Count mismatches:
• Add 1 for "(", subtract 1 for ")" if left > 0, else add to right.
• Line 17-19: BFS setup:
• Queue starts with (s, 0, left, right), seen tracks duplicates, result collects valid strings.
• Line 22-40: BFS loop:
• Line 24-25: Process each level until valid found.
• Line 27-30: If l and r are 0 and valid, add to result, mark found.
• Line 31-40: For each char:
• Keep it: Move idx up.
• Remove if "(" and l > 0, or ")" and r > 0, add new string to queue if unseen.
• Line 43-51: is_valid: Ensure balanced parentheses.
• Time Complexity: O(2^n) worst case, but pruning reduces it significantly.
• Space Complexity: O(n)—queue and seen set.

This is like a quick cleanup—fix it level-by-level!

Alternative Solution: DFS with Backtracking

Why an Alternative Approach?

DFS with backtracking explores all removal combos recursively—O(2^n) time, O(n) space. It’s less optimal but clearer for recursion fans, like trying every fix path-by-path—good for understanding but slower.

How It Works

Let’s think of this as a recursive fix:

• Step 1: Count mismatches.
• Step 2: Recurse, removing one parenthesis at a time, tracking counts.
• Step 3: Collect valid strings when counts hit zero.

It’s like a deep dive into fixes!

Step-by-Step Example

Example: s = "()())()"

• Count: left = 0, right = 1.
• DFS:
• "()())()", remove ")" at 1: "()()()", valid.
• "()())()", remove ")" at 4: "(())()", valid.
• Result: ["()()()", "(())()"].

Code for DFS Approach

Copy codeclass Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left = right = 0
        for char in s:
            if char == '(':
                left += 1
            elif char == ')':
                if left > 0:
                    left -= 1
                else:
                    right += 1

        result = set()

        def dfs(s, idx, l, r, curr):
            if l == 0 and r == 0 and self.is_valid(curr):
                result.add(curr)
                return
            if idx >= len(s) or l < 0 or r < 0:
                return

            if s[idx] == '(':
                dfs(s, idx + 1, l - 1, r, curr)  # Remove
                dfs(s, idx + 1, l, r, curr + '(')  # Keep
            elif s[idx] == ')':
                dfs(s, idx + 1, l, r - 1, curr)  # Remove
                dfs(s, idx + 1, l, r, curr + ')')  # Keep
            else:
                dfs(s, idx + 1, l, r, curr + s[idx])  # Letter

        dfs(s, 0, left, right, "")
        return list(result)

    def is_valid(self, s):
        count = 0
        for char in s:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0

• Time Complexity: O(2^n)—explores all combos.
• Space Complexity: O(n)—recursion stack.

It’s a recursive fix-fest!

Comparing the Two Solutions

• BFS (Best):
• Pros: O(2^n) optimized, O(n) space, minimal removals first.
• Cons: Queue management.
• DFS (Alternative):
• Pros: O(2^n) time, O(n) space, recursive clarity.
• Cons: Slower, explores more.

BFS wins for speed.

Additional Examples and Edge Cases

• "(": [""].
• "()())": ["()()", "(())"].
• "a": ["a"].

BFS is faster.

Complexity Breakdown

• BFS: Time O(2^n) reduced, Space O(n).
• DFS: Time O(2^n), Space O(n).

BFS rules.

Key Takeaways

• BFS: Level-by-level—fast!
• DFS: Dive deep—clear!
• Parentheses: Balance is key.
• Python Tip: Queues rock—see [Python Basics](/python/basics).

Final Thoughts: Balance Those Brackets

LeetCode 301: Remove Invalid Parentheses in Python is a brainy string puzzle. BFS with pruning zips to the fix, while DFS explores every path. Want more? Try LeetCode 20: Valid Parentheses or LeetCode 678: Valid Parenthesis String. Ready to snip? Head to Solve LeetCode 301 on LeetCode and clean up those parentheses today!