Remove Invalid Parentheses

▶

Steps

setup

Initialize queue and visited set

Start with the original string '()())()' in the queue and mark it visited to avoid repeats.

💡 Initialization ensures BFS starts from the original input and prevents revisiting the same strings.

Line:

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

💡 The BFS queue begins with the original string, setting the stage for level-by-level exploration.

compare

Process first string: check validity

Dequeue the string '()())()' and check if it is valid by counting parentheses balance.

💡 Checking validity determines if the current string can be part of the final answer or if further removals are needed.

Line:

curr = queue.popleft()
if is_valid(curr):

💡 The original string is invalid, so we must generate new strings by removing parentheses.

expand

Generate strings by removing one parenthesis (index 0)

Remove the parenthesis at index 0 '(' from '()())()' to create ')())()'. Since it is new, add to queue and visited.

💡 Removing one parenthesis generates new candidate strings to explore in BFS.

Line:

next_str = curr[:i] + curr[i+1:]
if next_str not in visited:
  visited.add(next_str)
  queue.append(next_str)

💡 Each removal creates a new node connected by an edge from the current string.

expand

Generate strings by removing one parenthesis (index 1)

Remove the parenthesis at index 1 ')' from '()())()' to create '(())()'. Add to queue and visited as new string.

💡 Each parenthesis removal explores a new candidate string for validity.

Line:

next_str = curr[:i] + curr[i+1:]
if next_str not in visited:
  visited.add(next_str)
  queue.append(next_str)

💡 Multiple children nodes can be generated from one parent by removing different parentheses.

expand

Generate strings by removing one parenthesis (index 2)

Remove the parenthesis at index 2 '(' from '()())()' to create '()))()'. Add to queue and visited.

💡 Systematically removing each parenthesis ensures all candidates are explored.

Line:

next_str = curr[:i] + curr[i+1:]
if next_str not in visited:
  visited.add(next_str)
  queue.append(next_str)

💡 The BFS tree expands with all possible one-removal strings.

compare

Process next string ')())()': check validity

Dequeue ')())()' and check if it is valid. It is invalid because it starts with a closing parenthesis.

💡 Validity check filters out invalid strings early to avoid unnecessary expansions.

Line:

curr = queue.popleft()
if is_valid(curr):

💡 Invalid strings are expanded further to find valid substrings.

expand

Generate children from ')())()' by removing one parenthesis (index 0)

Remove ')' at index 0 from ')())()' to get '())()'. Add to queue and visited.

💡 Removing parentheses from invalid strings generates new candidates closer to validity.

Line:

next_str = curr[:i] + curr[i+1:]
if next_str not in visited:
  visited.add(next_str)
  queue.append(next_str)

💡 New nodes represent strings with one fewer parenthesis than their parent.

compare

Process next string '(())()': check validity

Dequeue '(())()' and check if it is valid. It is valid because parentheses are balanced.

💡 Finding a valid string means we can add it to results and stop deeper exploration.

Line:

curr = queue.popleft()
if is_valid(curr):

💡 BFS ensures this is a minimal removal valid string.

compare

Process next string '()))()': check validity

Dequeue '()))()' and check if it is valid. It is invalid due to unbalanced parentheses.

💡 Invalid strings at this level are not expanded further because a valid string was found at this level.

Line:

curr = queue.popleft()
if is_valid(curr):

💡 Once a valid string is found, BFS stops expanding deeper levels to ensure minimal removals.

compare

Process next string '())()': check validity

Dequeue '())()' and check if it is valid. It is valid, so add to results.

💡 Finding another valid string at the same BFS level ensures all minimal removals are found.

Line:

curr = queue.popleft()
if is_valid(curr):

💡 Multiple valid strings can exist at the minimal removal level.

prune

Stop BFS and return results

Since valid strings were found at this BFS level, stop further expansions and return all valid strings collected.

💡 Stopping at the first valid level guarantees minimal removals and optimal solutions.

Line:

if found:
  break
return res

💡 BFS level-by-level ensures minimal removals and complete valid string set.

from typing import List
from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str) -> List[str]:
    res = []
    visited = set([s])  # STEP 1
    queue = deque([s])   # STEP 1
    found = False        # STEP 1

    while queue:         # STEP 2
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()  # STEP 2
            if is_valid(curr):      # STEP 8,10
                res.append(curr)   # STEP 8,10
                found = True       # STEP 8,10
            if found:
                continue          # STEP 9
            for i in range(len(curr)):  # STEP 3-5,7
                if curr[i] not in ('(', ')'):
                    continue
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
        if found:               # STEP 11
            break
    return res

if __name__ == "__main__":
    test_str = "()())()"
    print(remove_invalid_parentheses_bfs(test_str))

📊

Remove Invalid Parentheses - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how BFS ensures minimal removals and how pruning works by stopping deeper levels once valid strings are found.

Visiting: 0

0

Queue / Stack

0

Visiting: 0

0

Visiting: 0

Edge: 0 → 1

0

1

Queue / Stack

1

Visiting: 0

Edge: 0 → 2

0

1

2

Queue / Stack

12

Visiting: 0

Edge: 0 → 3

0

1

2

3

Queue / Stack

123

Visiting: 1

0

1

2

3

Queue / Stack

23

Visiting: 1

Edge: 1 → 4

0

1

2

3

4

Queue / Stack

234

Visiting: 2

0

1

2

3

4

Queue / Stack

34

Visiting: 3

0

1

2

3

4

Queue / Stack

4

Visiting: 4

0

1

2

3

4

Visiting: none

0

1

2

3

4

Key Takeaways

✓ BFS level-by-level traversal guarantees minimal removals to find valid strings.

This insight is hard to see from code alone because it requires understanding the search space and pruning logic visually.

✓ Once a valid string is found at a BFS level, deeper levels are not explored, optimizing performance.

This pruning step is subtle in code but clear when watching the queue stop growing after valid strings appear.

✓ Multiple valid strings can exist at the same minimal removal level, and BFS finds all of them.

Seeing multiple valid nodes at the same level helps understand why BFS is preferred over DFS here.

Practice

1. What is the time complexity of the backtracking with bitmask optimization approach for counting beautiful arrangements of size n?

medium

A. O(n * n!)

B. O(n^2)

C. O(n * 2^n)

D. O(n!)

Solution

1. Step 1: Identify the search space

   The algorithm explores permutations of n numbers, which is n! in worst case.

2. Step 2: Consider pruning and bitmask usage

   Bitmask helps track used numbers efficiently, pruning invalid branches but the total number of recursive calls is proportional to n * n! because for each position, up to n choices are tried.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores permutations with n choices per position, leading to O(n * n!) complexity [OK]

Hint: Backtracking permutations with bitmask -> O(n * n!) time [OK]

Common Mistakes:

• Confusing bitmask with exponential 2^n complexity
• Assuming polynomial due to pruning

2. Identify the bug in the following code snippet for counting beautiful arrangements:

medium

A. Line with 'bit = 1 << num' bit shift

B. Line with 'if (used & bit) == 0' check

C. Line with 'if pos > n:' condition

D. Line with recursive call 'backtrack(pos + 1, used | bit)'

Solution

1. Step 1: Analyze bit shift operation

   Bitmask uses 0-based indexing, so bit for number num should be 1 << (num - 1), not 1 << num.

2. Step 2: Consequence of incorrect bit shift

   Incorrect bit shifts cause wrong bits to be set/checked, leading to missing or duplicate counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct bit shift is critical for accurate used-state tracking [OK]

Hint: Bit shifts must be zero-based for bitmask [OK]

Common Mistakes:

• Off-by-one bit shifts
• Forgetting to unmark used numbers

3. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            # Bug: missing leading zero check
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

medium

A. Line with 'if i != index and num[index] == '0':' missing here

B. Line with 'curr_str = num[index:i+1]' (substring extraction)

C. Line with 'path[length_before:] = []' (backtracking cleanup)

D. Line with 'path.append('+'); path.append(curr_str)' (operator insertion)

Solution

1. Step 1: Identify handling of leading zeros

   The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".

2. Step 2: Confirm bug location

   This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check causes invalid operands [OK]

Hint: Leading zero check missing causes invalid operands [OK]

Common Mistakes:

• Confusing backtracking cleanup lines as bug
• Thinking substring extraction is buggy

4. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

5. Consider the following code snippet for palindrome partitioning. Which line contains a subtle bug that causes incorrect or duplicate partitions?

def partition(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start, path):
        if start == len(s):
            result.append(path)  # Line X
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

medium

A. Line 6: palindrome check misses single character substrings

B. Line X: appending path without copying causes shared references

C. Line 12: for loop range should be from start+1 to len(s)+1

D. Line 15: missing path.pop() after backtrack call

Solution

1. Step 1: Identify how results are stored

   Appending path directly stores a reference, so later modifications affect all stored results.

2. Step 2: Correct approach

   Use result.append(path[:]) to append a copy, preserving each partition snapshot.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Shared references cause incorrect final partitions [OK]

Hint: Always append a copy of path to results [OK]

Common Mistakes:

• Forgetting to copy path before appending
• Incorrect palindrome check boundaries
• Forgetting to pop after recursion