Reorganize String (No Two Adjacent Same)

▶

Steps

setup

Count character frequencies

Count the frequency of each character in the input string 'aab'. The counts are: 'a' -> 2, 'b' -> 1.

💡 Knowing character frequencies is essential to prioritize which character to place next to avoid adjacency conflicts.

Line:

freq = Counter(s)

💡 Frequency counts determine the initial priorities for the heap.

setup

Build max heap from frequencies

Create a max heap with elements (-frequency, character): [(-2, 'a'), (-1, 'b')]. Heapify to maintain max heap property.

💡 Using negative counts allows Python's min-heap to behave like a max heap, prioritizing characters with higher frequency.

Line:

max_heap = [(-count, ch) for ch, count in freq.items()]
heapq.heapify(max_heap)

💡 The heap now efficiently provides the character with the highest remaining frequency.

setup

Initialize previous character holder

Initialize variables prev_count = 0 and prev_char = '' to hold the previously used character for later re-insertion if needed.

💡 Holding the previous character prevents placing the same character twice in a row.

Line:

prev_count, prev_char = 0, ''

💡 This mechanism ensures no two adjacent characters are identical.

delete

Pop top character from heap

Pop the character with highest frequency from the heap: (-2, 'a'). This character will be appended to the result.

💡 Selecting the most frequent character first maximizes chances to place all characters without adjacency conflicts.

Line:

count, ch = heapq.heappop(max_heap)

💡 The root of the heap is always the next best character to use.

insert

Append character to result

Append character 'a' to the result list. Result is now ['a'].

💡 Appending the selected character builds the final string step by step.

Line:

result.append(ch)

💡 The result string grows with each selected character.

insert

Re-insert previous character if still available

Since prev_count = 0 (no previous character to reinsert), skip pushing anything back to the heap.

💡 No character is waiting to be reinserted after the first step.

Line:

if prev_count < 0:
    heapq.heappush(max_heap, (prev_count, prev_char))

💡 Only characters with remaining frequency are reinserted.

setup

Update previous character holder

Update prev_count and prev_char to (count + 1, ch) = (-2 + 1, 'a') = (-1, 'a'). This means one 'a' remains to be placed.

💡 Tracking remaining frequency of the last used character is crucial to avoid adjacency.

Line:

prev_count, prev_char = count + 1, ch

💡 The previous character is held for possible reinsertion in the next iteration.

delete

Pop top character from heap

Pop the next character with highest frequency: (-1, 'b').

💡 Selecting the next most frequent character ensures no two adjacent characters are the same.

Line:

count, ch = heapq.heappop(max_heap)

💡 Heap always provides the next best candidate character.

insert

Append character to result

Append character 'b' to the result list. Result is now ['a', 'b'].

💡 Appending characters builds the final string stepwise.

Line:

result.append(ch)

💡 The result string is constructed without adjacent duplicates.

insert

Re-insert previous character if still available

Previous character 'a' has prev_count = -1, so reinsert (-1, 'a') back into the heap for future use.

💡 Reinserting leftover characters ensures all characters are placed if possible.

Line:

if prev_count < 0:
    heapq.heappush(max_heap, (prev_count, prev_char))

💡 Characters are recycled until fully used or placement is impossible.

setup

Update previous character holder

Update prev_count and prev_char to (count + 1, ch) = (-1 + 1, 'b') = (0, 'b'). 'b' is fully used.

💡 Tracking when a character is fully used prevents unnecessary reinsertion.

Line:

prev_count, prev_char = count + 1, ch

💡 Characters with zero remaining frequency are not reinserted.

delete

Pop top character from heap

Pop the last character (-1, 'a') from the heap to append it to the result.

💡 Using the leftover character completes the string without adjacency conflicts.

Line:

count, ch = heapq.heappop(max_heap)

💡 Heap empties as characters are used up.

insert

Append character to result

Append character 'a' to the result list. Result is now ['a', 'b', 'a'].

💡 Appending the last character completes the output string.

Line:

result.append(ch)

💡 The final string is built with no two adjacent characters identical.

insert

Re-insert previous character if still available

Previous character 'a' has prev_count = 0, so no reinsertion is needed.

💡 No leftover characters remain to be reinserted.

Line:

if prev_count < 0:
    heapq.heappush(max_heap, (prev_count, prev_char))

💡 All characters have been placed.

compare

Check if result length matches input length

Check if the length of the result string 'aba' equals the input length 3. It does, so the result is valid.

💡 This check confirms if a valid rearrangement was possible.

Line:

if len(res_str) != len(s):
    return ""

💡 Successful rearrangement means no two adjacent characters are the same.

import heapq
from collections import Counter

def reorganizeString(s: str) -> str:
    freq = Counter(s)  # STEP 1
    max_heap = [(-count, ch) for ch, count in freq.items()]  # STEP 2
    heapq.heapify(max_heap)  # STEP 2
    prev_count, prev_char = 0, ''  # STEP 3
    result = []

    while max_heap:  # Loop starts
        count, ch = heapq.heappop(max_heap)  # STEP 4,8,12
        result.append(ch)  # STEP 5,9,13
        if prev_count < 0:  # STEP 6,10,14
            heapq.heappush(max_heap, (prev_count, prev_char))
        prev_count, prev_char = count + 1, ch  # STEP 7,11

    res_str = ''.join(result)
    if len(res_str) != len(s):  # STEP 15
        return ""
    return res_str

📊

Reorganize String (No Two Adjacent Same) - Watch the Algorithm Execute, Step by Step

Watching each heap operation and character selection step reveals how the greedy approach ensures no two adjacent characters are the same.

setupmax-heap

empty heap

heapifymax-heap

-2

0

-1

1

setupmax-heap

-2

0

-1

1

extract_maxmax-heap

-1

0

Added: "a"

insertmax-heap

-1

0

Added: "a"

insertmax-heap

-1

0

setupmax-heap

-1

0

extract_maxmax-heap

empty heap

Added: "b"

insertmax-heap

empty heap

Added: "b"

insertmax-heap

-1

0

setupmax-heap

-1

0

extract_maxmax-heap

empty heap

Added: "a"

insertmax-heap

empty heap

Added: "a"

insertmax-heap

empty heap

peekmax-heap

empty heap

Added: "aba"

Key Takeaways

✓ The max heap prioritizes characters by frequency, ensuring the most frequent character is placed first.

This insight is hard to see from code alone because the heap operations are abstract; visualization shows the priority clearly.

✓ Holding and reinserting the previous character prevents placing the same character twice consecutively.

This mechanism is subtle in code but critical; visualization reveals how the algorithm avoids adjacency conflicts.

✓ The algorithm terminates successfully only if the result length matches the input length, confirming a valid rearrangement.

This final check is easy to overlook in code but essential to detect impossible cases.

Practice

1. Given the following Python code for assigning cookies to children, what is the final returned value when g = [1, 2, 3] and s = [1, 1]?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace first iteration

   g and s sorted: g=[1,2,3], s=[1,1]. i=0, j=0, count=0. s[0]=1 ≥ g[0]=1 -> count=1, i=1, j=1.

2. Step 2: Trace second iteration

   i=1, j=1, count=1. s[1]=1 < g[1]=2 -> j=2. Loop ends as j=2 equals len(s).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only one cookie satisfies a child's greed [OK]

Hint: Trace pointer increments carefully [OK]

Common Mistakes:

• Counting cookies not sufficient for greed
• Off-by-one in loop conditions
• Ignoring pointer increments

2. Given the following code snippet implementing the optimal candy distribution algorithm, what is the final returned value when input ratings = [1, 0, 2]?

easy

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Trace left-to-right pass

   ratings = [1,0,2], candies init = [1,1,1] - i=1: ratings[1]=0 < ratings[0]=1, no change - i=2: ratings[2]=2 > ratings[1]=0, candies[2] = candies[1]+1 = 2 candies after pass: [1,1,2]

2. Step 2: Trace right-to-left pass

   i=1: ratings[1]=0 < ratings[2]=2, no change i=0: ratings[0]=1 > ratings[1]=0 and candies[0]=1 <= candies[1]=1, update candies[0] = candies[1]+1 = 2 candies after pass: [2,1,2] Sum = 2+1+2 = 5

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum matches expected output 5 [OK]

Hint: Sum candies after two passes for final answer [OK]

Common Mistakes:

• Forgetting to update candies in right-to-left pass
• Off-by-one errors in loops
• Misreading comparison operators

3. Consider the following buggy code for candy distribution. Which line contains the subtle bug that can cause incorrect candy counts?

medium

A. Line 3: candies initialized with zeros instead of ones

B. Line 5: loop starts from 1 instead of 0

C. Line 7: candies[i] updated without checking if greater than candies[i-1]

D. Line 9: condition candies[i] <= candies[i + 1] missing

Solution

1. Step 1: Check initialization of candies array

   Line 3 initializes candies with zeros, violating the problem requirement that each child must have at least one candy.

2. Step 2: Understand impact of zero initialization

   Zero candies can cause incorrect comparisons and final sums, failing test cases where minimum is 1 per child.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initialization must be at least 1 per child [OK]

Hint: Candies must start at 1, not 0 [OK]

Common Mistakes:

• Forgetting minimum candy per child
• Incorrect loop boundaries
• Missing update conditions

4. Identify the bug in the following code snippet for the Minimum Domino Rotations problem:

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return 0  # Bug here
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

medium

A. Incorrect initialization of rotations_a and rotations_b

B. Not incrementing rotations when both sides equal x

C. Returning rotations without checking both candidates

D. The return value 0 instead of -1 when no domino can be rotated to x

Solution

1. Step 1: Analyze early return condition

   If neither side matches candidate x, the function should return -1 to indicate failure, not 0.

2. Step 2: Impact of returning 0

   Returning 0 falsely indicates zero rotations needed, causing incorrect positive results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Returning -1 signals no solution; 0 misleads caller [OK]

Hint: Return -1 on failure, not 0 [OK]

Common Mistakes:

• Returning 0 instead of -1 on failure
• Overcounting rotations when both sides equal candidate

5. Suppose the problem is modified: instead of finding the largest monotone increasing digits number ≤ n, you want the largest monotone increasing digits number ≤ n that can reuse digits any number of times (digits can be repeated arbitrarily). Which approach correctly adapts the algorithm?

hard

A. Use the original greedy algorithm but allow digits after marker to be any digit less than or equal to the digit at marker-1

B. Sort the digits of n and build the largest monotone number by repeating the smallest digit as many times as needed

C. Use a backtracking approach to generate all monotone numbers with digits ≤ those in n, allowing reuse, and pick the largest ≤ n

D. Modify the greedy algorithm to decrement digits and set trailing digits to the digit at marker-1 instead of 9

Solution

1. Step 1: Understand digit reuse changes problem nature

   Allowing reuse means digits can be repeated arbitrarily, so greedy digit decrement and trailing 9 assignment no longer guarantee largest monotone number ≤ n.

2. Step 2: Backtracking enumerates all monotone numbers with digit reuse

   Backtracking can generate all monotone numbers with digits ≤ those in n, allowing reuse, then pick the largest ≤ n.

3. Step 3: Other options fail to handle reuse or produce incorrect numbers

   Sorting digits or modifying trailing digits to marker-1 digit does not guarantee largest monotone number with reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backtracking correctly handles reuse and monotonicity constraints [OK]

Hint: Digit reuse breaks greedy; backtracking needed for correctness [OK]

Common Mistakes:

• Trying to adapt greedy without full enumeration
• Assuming trailing digits can be set to 9 or marker digit
• Ignoring exponential complexity of reuse