Introduction

In this blog post, we will explore how to solve the LeetCode problem "301" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: s = "()())()" Output: ["(())()","()()()"] Example 2: Input: s = "(a)())()" Output: ["(a())()","(a)()()"] Example 3: Input: s = ")(" Output: [""] Constraints: 1 <= s.length <= 25 s consists of lowercase English letters and parentheses '(' and ')'. There will be at most 20 parentheses in s.

Explanation

• BFS Traversal: Use Breadth-First Search (BFS) to explore possible strings by iteratively removing parentheses.
  • Validity Check: At each step, check if the current string is valid using a simple counter-based approach.
  • Deduplication: Use a set to store visited strings and results to avoid redundant computations and ensure uniqueness in the final output.

• Runtime Complexity: O(n * 2ⁿ) - where n is the length of the string (in the worst case, each character could be a parenthesis, and we might have to explore all possible subsets). Storage Complexity: O(2ⁿ) - in the worst-case scenario where all substrings are added to the visited and result sets.

Code

    from collections import deque

def remove_invalid_parentheses(s: str) -> list[str]:
    """
    Removes the minimum number of invalid parentheses to make the input string valid.

    Args:
        s: The input string containing parentheses and letters.

    Returns:
        A list of unique strings that are valid with the minimum number of removals.
    """

    def is_valid(string: str) -> bool:
        """Checks if a string has valid parentheses."""
        count = 0
        for char in string:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
            if count < 0:
                return False
        return count == 0

    queue = deque([s])
    visited = {s}
    result = []
    found_valid = False

    while queue:
        curr_string = queue.popleft()

        if is_valid(curr_string):
            result.append(curr_string)
            found_valid = True

        if found_valid:
            continue

        for i in range(len(curr_string)):
            if curr_string[i] not in ('(', ')'):
                continue

            new_string = curr_string[:i] + curr_string[i+1:]

            if new_string not in visited:
                visited.add(new_string)
                queue.append(new_string)

    return result