Rearrange String k Distance Apart

▶

Steps

setup

Count frequencies and build max heap

Count the frequency of each character in the input string and create a max heap with negative counts to prioritize the most frequent characters.

💡 Counting frequencies is the foundation; building the max heap lets us always pick the character with the highest remaining count.

Line:

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

💡 The heap now contains all characters prioritized by frequency, ready for greedy selection.

delete

Pop most frequent character 'a' from heap

Pop the root of the max heap, which is the character 'a' with frequency 2, to append it to the result string.

💡 Removing the top character lets us place it in the result, starting the rearrangement.

Line:

count, char = heapq.heappop(max_heap)
res.append(char)

💡 The algorithm greedily picks the most frequent character available.

insert

Add 'a' with decremented count to queue

Add the character 'a' with updated count (-1) to the queue to enforce the k-distance constraint before it can be reused.

💡 The queue acts as a cooldown window to prevent immediate reuse of the same character.

Line:

queue.append((char, count + 1))  # count + 1 because count is negative

💡 Characters must wait k steps before being pushed back to the heap if still available.

delete

Pop most frequent character 'b' from heap

Pop the root of the heap, character 'b' with frequency 2, to append it to the result string.

💡 Continuing to pick the most frequent character available to build the result.

Line:

count, char = heapq.heappop(max_heap)
res.append(char)

💡 The heap dynamically updates as characters are used.

insert

Add 'b' with decremented count to queue

Add character 'b' with updated count (-1) to the queue to maintain the k-distance constraint.

💡 Queue size is still less than k, so no character is released back to the heap yet.

Line:

queue.append((char, count + 1))

💡 Characters wait in the queue before they can be reused.

delete

Pop most frequent character 'c' from heap

Pop character 'c' with frequency 2 from the heap and append it to the result string.

💡 Selecting the next most frequent character to continue building the result.

Line:

count, char = heapq.heappop(max_heap)
res.append(char)

💡 Heap always gives the next best candidate character.

insert

Add 'c' with decremented count to queue

Add character 'c' with updated count (-1) to the queue. Queue size now equals k (3).

💡 Queue reached size k, so we will now release the oldest character from the queue.

Line:

queue.append((char, count + 1))

💡 Once queue size hits k, characters can be recycled if they still have remaining count.

insert

Pop front character 'a' from queue and reinsert into heap

Pop the oldest character 'a' from the queue. Since it still has count -1, push it back into the heap for reuse.

💡 Reinserting characters after cooldown allows them to be used again while maintaining spacing.

Line:

front_char, front_count = queue.popleft()
if front_count < 0:
    heapq.heappush(max_heap, (front_count, front_char))

💡 The queue enforces the k-distance by delaying reinsertion.

delete

Pop most frequent character 'a' from heap

Pop character 'a' with frequency -1 from the heap and append it to the result string.

💡 Reusing 'a' after cooldown to continue building the valid rearrangement.

Line:

count, char = heapq.heappop(max_heap)
res.append(char)

💡 Characters can be reused after waiting k steps.

insert

Add 'a' with decremented count to queue

Add character 'a' with updated count (0) to the queue. Since count is zero, it will not be reinserted later.

💡 Characters with zero remaining count are not recycled.

Line:

queue.append((char, count + 1))

💡 The algorithm tracks when characters are fully used.

insert

Pop front character 'b' from queue and reinsert into heap

Pop character 'b' from the queue. Since it still has count -1, push it back into the heap.

💡 Characters with remaining count are recycled after cooldown.

Line:

front_char, front_count = queue.popleft()
if front_count < 0:
    heapq.heappush(max_heap, (front_count, front_char))

💡 Queue enforces spacing by delaying reinsertion.

delete

Pop most frequent character 'b' from heap

Pop character 'b' with frequency -1 from the heap and append it to the result string.

💡 Reuse 'b' after cooldown to continue valid rearrangement.

Line:

count, char = heapq.heappop(max_heap)
res.append(char)

💡 Characters are reused only after waiting k steps.

insert

Add 'b' with decremented count to queue

Add character 'b' with updated count (0) to the queue. It will not be reinserted later.

💡 Characters with zero count are not recycled.

Line:

queue.append((char, count + 1))

💡 Tracking when characters are fully used prevents infinite loops.

insert

Pop front character 'c' from queue and reinsert if needed

Pop character 'c' from the queue. Since count is -1, reinsert into heap for reuse.

💡 Characters with remaining count are recycled after cooldown.

Line:

front_char, front_count = queue.popleft()
if front_count < 0:
    heapq.heappush(max_heap, (front_count, front_char))

💡 Queue enforces spacing by delaying reinsertion.

delete

Pop most frequent character 'c' from heap

Pop character 'c' with frequency -1 from the heap and append it to the result string.

💡 Reuse 'c' after cooldown to complete the rearrangement.

Line:

count, char = heapq.heappop(max_heap)
res.append(char)

💡 Characters are reused only after waiting k steps.

insert

Add 'c' with decremented count to queue

Add character 'c' with updated count (0) to the queue. No reinsertion will happen as count is zero.

💡 All characters have been used up now.

Line:

queue.append((char, count + 1))

💡 The algorithm finishes when heap is empty and no characters remain.

insert

Pop front character 'a' from queue (count=0), no reinsertion

Pop character 'a' from the queue. Count is zero, so it is not reinserted into the heap.

💡 Characters with zero count are discarded after cooldown.

Line:

front_char, front_count = queue.popleft()
if front_count < 0:
    heapq.heappush(max_heap, (front_count, front_char))

💡 Queue empties as characters are fully used.

insert

Pop front character 'b' from queue (count=0), no reinsertion

Pop character 'b' from the queue. Count is zero, so it is not reinserted into the heap.

💡 Characters with zero count are discarded after cooldown.

Line:

front_char, front_count = queue.popleft()
if front_count < 0:
    heapq.heappush(max_heap, (front_count, front_char))

💡 Queue empties as characters are fully used.

insert

Pop front character 'c' from queue (count=0), no reinsertion

Pop character 'c' from the queue. Count is zero, so it is not reinserted into the heap.

💡 All characters have been fully used and queue is now empty.

Line:

front_char, front_count = queue.popleft()
if front_count < 0:
    heapq.heappush(max_heap, (front_count, front_char))

💡 Queue is empty, heap is empty, algorithm ends.

reconstruct

Final result assembled and verified

The result string "abcabc" has length equal to input string length, so it is returned as the valid rearrangement.

💡 The algorithm successfully rearranged the string with characters at least k distance apart.

Line:

return ''.join(res) if len(res) == len(s) else ""

💡 The greedy heap and queue approach ensures valid rearrangement if possible.

from collections import Counter, deque
import heapq

def rearrangeString(s, k):
    if k == 0:
        return s
    freq = Counter(s)  # STEP 1
    max_heap = [(-count, char) for char, count in freq.items()]  # STEP 1
    heapq.heapify(max_heap)  # STEP 1
    queue = deque()
    res = []

    while max_heap:  # STEP 2 to 19 loop
        count, char = heapq.heappop(max_heap)  # STEP 2,4,6,9,12,15
        res.append(char)  # STEP 2,4,6,9,12,15
        queue.append((char, count + 1))  # STEP 3,5,7,10,13,16
        if len(queue) < k:
            continue
        front_char, front_count = queue.popleft()  # STEP 8,11,14,17,18,19
        if front_count < 0:
            heapq.heappush(max_heap, (front_count, front_char))  # STEP 8,11,14

    return ''.join(res) if len(res) == len(s) else ""  # STEP 20

📊

Rearrange String k Distance Apart - Watch the Algorithm Execute, Step by Step

Watching each heap operation and queue update reveals how the algorithm ensures characters are spaced at least k apart, which is hard to grasp from code alone.

heapifymax-heap

-2,a

0

-2,b

1

-2,c

2

extract_maxmax-heap

-2,b

0

-2,c

1

Added: "a"

insertmax-heap

-2,b

0

-2,c

1

extract_maxmax-heap

-2,c

0

Added: "b"

insertmax-heap

-2,c

0

extract_maxmax-heap

empty heap

Added: "c"

insertmax-heap

empty heap

insertmax-heap

-1,a

0

extract_maxmax-heap

empty heap

Added: "a"

insertmax-heap

empty heap

insertmax-heap

-1,b

0

extract_maxmax-heap

empty heap

Added: "b"

insertmax-heap

empty heap

insertmax-heap

-1,c

0

extract_maxmax-heap

empty heap

Added: "c"

insertmax-heap

empty heap

insertmax-heap

empty heap

insertmax-heap

empty heap

insertmax-heap

empty heap

peekmax-heap

empty heap

Added: "abcabc"

Key Takeaways

✓ The max heap always provides the character with the highest remaining frequency to place next.

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

✓ The queue enforces the k-distance constraint by delaying reinsertion of recently used characters.

Seeing the queue fill and release characters after k steps clarifies how spacing is maintained.

✓ Characters with zero remaining count are discarded and not reinserted, signaling completion of their usage.

This prevents infinite loops and ensures the algorithm terminates correctly, which is subtle in code.

Practice

1. Given the following Python code for MedianFinder, what is the median after adding numbers 1, 5, and 2 in that order?

easy

A. 1.5

B. 2.0

C. 2

D. 3

Solution

1. Step 1: Insert 1

   low = [-1], high = [], median = 1 (only one element)

2. Step 2: Insert 5

   5 > 1, so push to high: high = [5], low = [-1]. Balanced heaps, median = (1 + 5)/2 = 3.0

3. Step 3: Insert 2

   2 <= 5 but > 1, so push to low: low = [-2, -1], high = [5]. Balance: low_size=2, high_size=1, median = top of low = 2.0

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Median after 3 inserts is 2.0 -> [OK]

Hint: Median after odd inserts is top of larger heap [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Incorrect median calculation for odd number of elements
• Confusing max-heap sign inversion

2. Given the following Python code for computing sliding window medians, what is the output when nums = [1, 3, -1] and k = 3?

easy

A. [1.0]

B. [1.0, 3.0]

C. [1.0, -1.0]

D. [3.0]

Solution

1. Step 1: Initialize window and compute median

   Window = [1, 3, -1] sorted -> [-1, 1, 3], median at index 1 (k//2) is 1.0

2. Step 2: Loop from i=k to len(nums)

   Since len(nums) = 3 and k=3, loop does not run, so only one median computed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one window median computed [OK]

Hint: No sliding when window size equals array length [OK]

Common Mistakes:

• Assuming loop runs even when window covers entire array
• Misindexing median for odd k
• Returning multiple medians incorrectly

3. Given the following Python code implementing the optimal approach for minimizing deviation, what is the final returned value when the input is [1, 2, 3, 4]?

import heapq

def minimumDeviation(nums):
    heap = []
    min_val = float('inf')
    for num in nums:
        if num % 2 == 1:
            num *= 2
        min_val = min(min_val, num)
        heapq.heappush(heap, -num)  # max heap by pushing negative

    min_dev = float('inf')
    while True:
        max_val = -heapq.heappop(heap)
        min_dev = min(min_dev, max_val - min_val)
        if max_val % 2 == 0:
            max_val //= 2
            min_val = min(min_val, max_val)
            heapq.heappush(heap, -max_val)
        else:
            break
    return min_dev

print(minimumDeviation([1,2,3,4]))

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Normalize input and build max-heap

   Input [1,2,3,4] becomes [2,2,6,4] after doubling odds. min_val = 2. Heap = [-6,-4,-2,-2].

2. Step 2: Iteratively reduce max and update min_dev

   Pop max=6, min_dev=6-2=4. Halve 6 -> 3, min_val=2, push -3. Pop max=4, min_dev=4-2=2. Halve 4 -> 2, min_val=2, push -2. Pop max=3, min_dev=2-2=0. 3 is odd, stop. Minimum deviation found is 1 (from earlier step).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final returned value matches expected minimal deviation [OK]

Hint: Doubling odds first and halving max even values reduces deviation [OK]

Common Mistakes:

• Forgetting to double odd numbers initially
• Stopping too early without halving max even values
• Miscomputing min_val after halving

4. What is the time complexity of the optimal balanced two heaps approach with indexed removal (using a balanced BST or multiset) for computing the median of every sliding window of size k in an array of length n?

medium

A. O(n log n)

B. O(n log k)

C. O(n k)

D. O(n k log k)

Solution

1. Step 1: Identify operations per window slide

   Each slide requires removing one element and inserting another into balanced BST/multiset, each O(log k).

2. Step 2: Calculate total complexity

   There are n-k+1 windows, so total complexity is O(n log k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Balanced BST operations cost O(log k) per insertion/removal [OK]

Hint: Each insertion/removal costs O(log k), done n times [OK]

Common Mistakes:

• Confusing n and k in complexity
• Assuming sorting each window (O(k log k)) per slide
• Ignoring log factor in balanced BST operations

5. Suppose the problem is modified so that intervals can be reused multiple times when finding the next interval (i.e., the same interval can be the next interval for multiple intervals). Which modification to the two heaps approach correctly handles this variant?

hard

A. Use a min-heap instead of max-heap for max_start_heap to simplify reuse logic.

B. Remove the pushing back of unused candidates to avoid duplicates in the heap.

C. After popping candidates from max_start_heap, push all candidates back into the heap regardless of selection.

D. Sort intervals by start and use binary search instead of heaps for reuse.

Solution

1. Step 1: Understand reuse requirement

   Intervals can be reused multiple times, so popping from max_start_heap must not remove intervals permanently.

2. Step 2: Modify heap management

   After extracting candidates, push all candidates back into max_start_heap to keep intervals available for future matches.

3. Step 3: Evaluate other options

   Removing push back loses intervals, min-heap breaks logic, and sorting + binary search is valid but changes approach.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Reinserting candidates preserves intervals for reuse [OK]

Hint: Reinsert candidates to allow multiple reuse [OK]

Common Mistakes:

• Not reinserting candidates losing intervals
• Switching heap type incorrectly
• Ignoring reuse requirement