We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Invalid Parentheses

Difficulty: Hard

Problem Description

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Key Insights

  • The goal is to generate all possible valid strings by removing invalid parentheses.
  • A string is considered valid if every opening parenthesis has a corresponding closing parenthesis.
  • We can utilize breadth-first search (BFS) to explore all possible states of the string after removing parentheses.
  • We need to track the minimum number of removals to ensure we only consider valid strings reached with this minimum.

Space and Time Complexity

Time Complexity: O(2^n) - In the worst case, we may generate all possible subsets of the string. Space Complexity: O(n) - Space is needed for the queue in BFS and the set of valid results.

Solution

The solution employs a breadth-first search (BFS) approach to explore all possible strings formed by removing parentheses. We maintain a queue for BFS and a set to keep track of already seen strings to avoid processing duplicates. The algorithm checks each string for validity and stops when it finds the first valid strings, ensuring that they are reached with the minimum number of removals.

  1. Initialize a queue with the original string and a set to keep track of visited strings.
  2. Continue the BFS until we find valid strings.
  3. For each string, generate all possible strings by removing one parenthesis at a time.
  4. Check if the generated string is valid. If it is, add it to the results list.
  5. Stop the search once valid strings are found at the current level of BFS to ensure minimum removals.

Code Solutions

from collections import deque

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

    results = set()
    queue = deque([s])
    found = False

    while queue:
        current = queue.popleft()

        if is_valid(current):
            results.add(current)
            found = True
        
        if found:
            continue  # Do not generate further strings if we've found valid ones

        for i in range(len(current)):
            if current[i] in ('(', ')'):
                next_string = current[:i] + current[i+1:]
                if next_string not in results:
                    queue.append(next_string)

    return list(results)
← Back to All Questions