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. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

Hint: Remember to convert k to zero-based before indexing [OK]

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

2. 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

3. The following code attempts to solve N-Queens using bitmask backtracking. Which line contains a subtle bug that can cause invalid solutions or missed solutions?

medium

A. Line extracting rightmost 1-bit as position

B. Line updating diag1 and diag2 with incorrect bit shifts in recursive call

C. Line computing available_positions with bitmask and negation

D. Line resetting board[row][col] to '.' after recursion

Solution

1. Step 1: Identify bit shift directions for diagonals

   diag1 (major diagonal) must be shifted left by 1, diag2 (minor diagonal) shifted right by 1 to reflect next row attacks.

2. Step 2: Check recursive call shifts

   The code incorrectly shifts diag1 right and diag2 left, reversing the attack directions, causing invalid pruning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct diagonal shifts are diag1 << 1 and diag2 >> 1 [OK]

Hint: Diagonal attack masks must shift opposite directions each row [OK]

Common Mistakes:

• Swapping diag1 and diag2 shifts
• Not resetting board after recursion
• Incorrect bitmask negation

4. What is the time complexity of the optimal factorial-based algorithm to find the k-th permutation of n numbers, and why?

medium

A. O(n^2) because each of the n iterations involves removing an element from a list of size up to n.

B. O(n!) because it generates all permutations internally.

C. O(n log n) due to sorting operations inside the algorithm.

D. O(n) because factorial computations and indexing are constant time per iteration.

Solution

1. Step 1: Analyze the main loop

   The algorithm runs a loop n times to select each digit of the permutation.

2. Step 2: Consider list removal cost

   Removing an element from the numbers list is O(n) in worst case, so total is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each iteration's pop is linear, leading to quadratic time [OK]

Hint: List pop at arbitrary index costs O(n), not O(1) [OK]

Common Mistakes:

• Assuming factorial computations dominate time
• Thinking it's O(n) due to fixed loop count
• Confusing factorial precomputation with sorting

5. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

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

Common Mistakes:

• Forgetting to copy before appending results in duplicate references