How do you solve Remove Invalid Parentheses on LeetCode?

Remove Invalid Parentheses (LeetCode #301) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Generating all possible strings is necessary to find valid combinations.

What is the brute force solution for Remove Invalid Parentheses?

The brute force approach for Remove Invalid Parentheses is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force method involves generating all possible combinations of the string by removing parentheses and checking each combination for validity. This approach ensures we explore every possibility but can be inefficient due to the exponential number of combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Remove Invalid Parentheses?

Remove Invalid Parentheses uses the following concepts: String, Backtracking, Breadth-First Search. The recommended patterns to study are: Backtracking, Breadth-First Search.

What are the interview tips for Remove Invalid Parentheses?

Explain your thought process clearly while coding. Discuss edge cases and how your solution handles them. Practice writing both brute force and optimal solutions.

What are common mistakes when solving Remove Invalid Parentheses?

Not checking for validity after each removal. Failing to handle edge cases like empty strings.

#301

Remove Invalid Parentheses

Hard

StringBacktrackingBreadth-First SearchBacktrackingBreadth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a breadth-first search (BFS) approach to explore valid strings level by level, ensuring we only generate valid strings with the minimum number of removals. This method is efficient and avoids unnecessary checks.

⚙️

Algorithm

4 steps

1Step 1: Count the number of misplaced '(' and ')' in the string.
2Step 2: Use a queue to perform BFS, starting with the original string.
3Step 3: For each string, generate all possible strings by removing one parenthesis and check for validity.
4Step 4: Stop when the first valid string is found and collect all unique valid strings.

solution.py26 lines

1# Full working Python code
2from collections import deque
3
4def is_valid(s):
5    count = 0
6    for char in s:
7        if char == '(': count += 1
8        if char == ')': count -= 1
9        if count < 0: return False
10    return count == 0
11
12def remove_invalid_parentheses(s):
13    result = set()
14    queue = deque([s])
15    found = False
16    while queue:
17        current = queue.popleft()
18        if is_valid(current):
19            result.add(current)
20            found = True
21        if found: continue
22        for i in range(len(current)):
23            if current[i] in '()':
24                next_str = current[:i] + current[i+1:]
25                queue.append(next_str)
26    return list(result)

ℹ

Complexity note: The time complexity is O(n) because we only traverse the string a limited number of times, and we use a set to store unique valid strings, which takes linear time.

1Generating all possible strings is necessary to find valid combinations.
2Using BFS ensures we explore the shortest paths to valid strings first.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.