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 Python code for generating parentheses, what is the content of result after calling generateParenthesis(2)?

easy

A. ['((', '))']

B. ['()()', '(())']

C. ['(())', '()()']

D. ['()()', '(()']

Solution

1. Step 1: Trace backtrack calls for n=2

   Sequences generated are '(())' and '()()' in that order due to DFS with backtracking.

2. Step 2: Confirm order and validity

   Both sequences are valid balanced parentheses of length 4, matching expected output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches known valid sequences for n=2 [OK]

Hint: Backtracking generates sequences in DFS order [OK]

Common Mistakes:

• Confusing order of sequences
• Including invalid partial sequences

2. You are given a partially filled 9x9 grid where each row, column, and 3x3 sub-box must contain digits 1 through 9 without repetition. Which algorithmic approach guarantees finding a valid solution if one exists?

easy

A. Greedy algorithm that fills cells with the first valid digit found

B. Breadth-first search exploring all possible digit placements simultaneously

C. Dynamic programming by storing subproblems of partially filled grids

D. Backtracking with constraint propagation and heuristic ordering of empty cells

Solution

1. Step 1: Understand problem constraints

   The problem requires filling cells respecting row, column, and box constraints, which is a classic constraint satisfaction problem.

2. Step 2: Identify algorithm that guarantees solution

   Backtracking with constraint propagation prunes invalid choices early, and heuristic ordering reduces branching, ensuring completeness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Constraint propagation + heuristic ordering is standard for Sudoku solvers [OK]

Hint: Constraint satisfaction problems need backtracking with pruning [OK]

Common Mistakes:

• Assuming greedy or BFS alone can solve Sudoku efficiently

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

4. Examine the following snippet from an optimized Sudoku solver. Which line contains a subtle bug that can cause incorrect solutions or failure to backtrack properly?

def backtrack():
    if not empties:
        return True
    empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
    r, c = empties[0]
    for ch in get_candidates(r, c):
        board[r][c] = ch
        rows[r].add(ch)
        cols[c].add(ch)
        boxes[(r//3)*3 + c//3].add(ch)
        empties.pop(0)
        if backtrack():
            return True
        # Undo changes
        board[r][c] = '.'
        rows[r].remove(ch)
        cols[c].remove(ch)
        boxes[(r//3)*3 + c//3].remove(ch)
        empties.insert(0, (r, c))
    return False

medium

A. Line that pops the first empty cell from empties

B. Line that sorts empties by candidate count

C. Line that adds ch to rows[r]

D. Line that resets board[r][c] to '.' after backtracking

Solution

1. Step 1: Identify mutation of empties list

   The line popping empties[0] removes the cell but is never restored on backtrack failure.

2. Step 2: Consequence of missing restoration

   Without re-adding the cell to empties after failed recursion, future calls miss this cell, causing incorrect state and solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking requires undoing all changes including empties list [OK]

Hint: Backtracking must undo all state changes, including empties list [OK]

Common Mistakes:

• Forgetting to restore empties after pop
• Assuming board reset is sufficient

5. Suppose the problem is modified so that numbers can be reused multiple times in the arrangement. Which change to the backtracking algorithm correctly adapts to this variant?

hard

A. Keep the 'used' bitmask but reset bits after each recursive call to allow reuse.

B. Remove the 'used' bitmask and allow all numbers at every position, checking divisibility only.

C. Use a frequency array to track counts of each number and decrement/increment during recursion.

D. Modify the divisibility condition to allow partial matches and keep the bitmask unchanged.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means numbers are no longer unique per position, so tracking used numbers is unnecessary.

2. Step 2: Adapt algorithm

   Removing the 'used' bitmask and checking only divisibility conditions at each position correctly counts valid arrangements with reuse.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without uniqueness constraint, 'used' tracking is redundant [OK]

Hint: Reuse means no need to track used numbers [OK]

Common Mistakes:

• Trying to reset bitmask bits incorrectly
• Using frequency arrays unnecessarily