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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Invalid Parentheses

Number: 301

Difficulty: Hard

Paid? No

Companies: Meta, TikTok, Deliveroo, Yandex, Bloomberg, Adobe, Microsoft

Problem Description

Given a string s containing parentheses and lowercase letters, remove the minimum number of invalid parentheses so that the resulting string is valid. Return all possible valid strings (without duplicates) that can be obtained after the minimum removals. The answer can be returned in any order.

Key Insights

  • Use BFS to generate all possible strings by removing one parenthesis at a time.
  • Stop the BFS once valid strings are found at the current level (to ensure minimum removals).
  • Use a set to avoid processing the same string multiple times.
  • Use a helper function to check if a string has valid parentheses.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst-case, as each character could be removed leading to exploring 2^n possibilities. Space Complexity: O(2^n) for storing all unique intermediate strings in the worst-case.

Solution

We solve this problem using a Breadth-First Search (BFS) approach. Start with the original string and generate all possible strings by removing one parenthesis at each step. For every generated string, check if it is valid using a helper function that traverses the string and maintains a balance counter. As soon as valid expressions are found at a particular level of BFS, add them to the result list and do not proceed to deeper levels. This ensures we remove the minimal number of parentheses. Data structures used include a queue for BFS and a set for visited strings to avoid duplicates.

Code Solutions

# Python solution using BFS
from collections import deque

def removeInvalidParentheses(s):
    # Helper function to check if a string is valid.
    def isValid(string):
        count = 0
        for char in string:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0

    result = []
    visited = set([s])  # Set to avoid re-processing the same string
    queue = deque([s])
    found = False  # Flag indicating if we've found a valid expression at current level

    while queue:
        current = queue.popleft()
        if isValid(current):
            result.append(current)
            found = True
        # Continue exploring only if a valid expression hasn't been found at this BFS level.
        if found:
            continue
        for i in range(len(current)):
            # Skip non-parenthesis characters.
            if current[i] != '(' and current[i] != ')':
                continue
            next_str = current[:i] + current[i+1:]
            if next_str not in visited:
                visited.add(next_str)
                queue.append(next_str)
    return result

# Example usage:
# print(removeInvalidParentheses("()())()"))
← Back to All Questions