NUHMAN.com

Introduction

LeetCode 301: Remove Invalid Parentheses asks us to remove the minimum number of invalid parentheses to make the input string valid. A valid parentheses string is one where the parentheses are balanced: for each opening parenthesis (, there is a corresponding closing parenthesis ), and the parentheses are properly nested.

The goal is to find all possible valid strings that can be obtained by removing the least number of parentheses and return them.

Problem Statement

Given a string s that contains parentheses and other characters, return all possible strings that can be obtained by removing the minimum number of invalid parentheses to make the input string valid.

Note:

• The answer must be a list of strings without duplicates.
• A valid parentheses string is one where the parentheses are properly balanced.

Example

python

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

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

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

✅ Step-by-Step Solution

🧠 Intuition

To solve this problem efficiently, we can use Breadth-First Search (BFS) to explore all possible ways of removing parentheses. The main idea is to:

1. Start with the original string.
2. Perform BFS to generate all possible strings by removing one parenthesis at each step.
3. Check validity for each string.
4. Stop early when we find valid strings at the current level because any valid string with fewer removals has already been encountered.

We need to ensure that we don't explore the same string more than once, which can be done using a set to track already visited strings.

✅ Approach

1. BFS Exploration:

• Start with the given string and add it to the queue.
• For each string in the queue, generate all possible strings by removing one parenthesis at each step.
• Check whether each generated string is valid.
• If valid, store it in the result list and stop further exploration from that string.

1. Validation:

• A string is valid if, by scanning from left to right, we never encounter more closing parentheses ) than opening parentheses (, and at the end, the count of opening and closing parentheses should be equal.

1. Optimization:

• Use a set to avoid processing the same string multiple times.
• Once we find any valid strings at a certain level of BFS, we don't need to go deeper as we are guaranteed that those valid strings are the result with the minimum number of removals.

✅ Python Code (BFS Solution)

python

from collections import deque

class Solution:
    def removeInvalidParentheses(self, s: str):
        def isValid(string):
            count = 0
            for char in string:
                if char == '(':
                    count += 1
                elif char == ')':
                    count -= 1
                if count < 0:  # More ')' than '('
                    return False
            return count == 0  # Balanced if count is 0

        # Initialize BFS queue and visited set
        queue = deque([s])
        visited = set([s])
        result = []
        found = False

        while queue:
            current = queue.popleft()
            
            # If a valid string is found, add to result
            if isValid(current):
                result.append(current)
                found = True

            # If we've found valid strings, don't go deeper
            if found:
                continue

            # Generate all possible strings by removing one parenthesis
            for i in range(len(current)):
                if current[i] not in ('(', ')'):
                    continue
                next_string = current[:i] + current[i+1:]
                if next_string not in visited:
                    visited.add(next_string)
                    queue.append(next_string)

        return result

🧪 How It Works

1. BFS Exploration:

• We start with the input string and add it to the queue. Then, for each string, we generate all possible strings by removing one parenthesis at a time and check if the new string has been visited before. If it hasn't been visited, we add it to the queue.

1. Validation:

• The isValid function checks if a string has balanced parentheses. It uses a counter to track the balance between opening and closing parentheses as it scans through the string. If the counter goes negative at any point, the string is invalid. The string is valid if the counter is zero at the end.

1. Stopping Condition:

• Once a valid string is found, we stop further exploration for strings that are at the same level of BFS because any valid string with fewer parentheses removed will be found first.

1. Result Compilation:

• The result list stores all valid strings, and we ensure there are no duplicates by using a set for the visited strings.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n * 2^n)Space ComplexityO(n * 2^n)

• Time Complexity: The time complexity depends on the number of possible strings generated by removing parentheses. In the worst case, we generate up to 2^n strings, and for each string, we check its validity in O(n) time. Thus, the overall time complexity is O(n * 2^n).
• Space Complexity: The space complexity is dominated by the storage required for the queue and visited set, both of which can grow up to O(n * 2^n) in the worst case.

🔍 Edge Cases

1. Empty String:

• If the input string is empty, the result should be an empty list because there are no parentheses to remove.

1. String with No Parentheses:

• If the input string doesn't contain any parentheses, the string is already valid, so the result should be a list containing the original string.

1. All Parentheses are Invalid:

• If all parentheses in the string are invalid (e.g., ")("), the valid solution could be an empty string.

1. No Valid Solution:

• If the input string is such that no valid parentheses arrangement can be formed (e.g., ")("), the result should be [""].

✅ Conclusion

LeetCode 301: Remove Invalid Parentheses is a problem that challenges us to find all possible valid strings formed by removing the minimum number of invalid parentheses. The BFS approach is efficient for this problem as it allows us to explore all possible valid strings level by level while ensuring that we only consider valid strings with the minimum number of removals.

• The BFS solution ensures that we explore all valid strings and stop early once we find valid solutions at the current level of exploration.
• The isValid function efficiently checks whether a string is a valid parentheses string by maintaining a counter.

This approach allows us to solve the problem optimally while keeping track of visited states to avoid redundant calculations.