NUHMAN.com

📘 Problem Statement

Given a string s and an integer k, rearrange the string such that the same characters are at least k distance apart. If not possible, return an empty string.

Constraints:

• 1 <= s.length <= 10^4
• 0 <= k <= s.length

🔧 Example

python

Input: s = "aabbcc", k = 3
Output: "abcabc"

Input: s = "aaabc", k = 3
Output: ""

🧠 Key Idea

To space out characters by at least k, we want to:

1. Always pick the most frequent character not used in the last k positions.
2. Use a greedy approach with a max heap to prioritize high-frequency letters.
3. Use a queue to manage the cooldown of characters.

📚 Data Structures Used

• Max Heap: To pick the most frequent available character.
• Queue (FIFO): To track the cooldown of characters over k distances.

🐍 Python Code

python

from collections import Counter, deque
import heapq

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k == 0:
            return s

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

        result = []
        wait_queue = deque()  # stores (freq, char, ready_time)
        time = 0

        while max_heap or wait_queue:
            if wait_queue and wait_queue[0][2] == time:
                heapq.heappush(max_heap, (wait_queue.popleft()[0], wait_queue[0][1]))

            if max_heap:
                freq, char = heapq.heappop(max_heap)
                result.append(char)
                if freq + 1 < 0:
                    wait_queue.append((freq + 1, char, time + k))
            else:
                if wait_queue:
                    return ""  # no valid char available now
            time += 1

        return "".join(result)

🔍 Step-by-Step Explanation

1. Count Frequencies

python

freq_map = Counter(s)

2. Initialize Max Heap

python

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

• Use negative frequencies since Python’s heapq is a min-heap.

3. Use Wait Queue to Enforce k-Distance

python

wait_queue = deque()  # (freq, char, ready_time)

• Characters in cooldown wait for k time units.

4. Build Result

• At each time t, check if any character's cooldown is done and re-add it to the heap.
• Pick the top of the heap and use it.
• Push it to the queue with its next available time.

5. Edge Case: No Valid Char Available

python

if wait_queue and not max_heap:
    return ""

🧪 Example Trace

Input: "aabbcc", k = 3

• Char frequencies: {a:2, b:2, c:2}
• Sequence: pick a, then b, then c, repeat.
• Output: "abcabc"

⏱️ Time & Space Complexity

OperationComplexityTimeO(n log n)SpaceO(n)

🧵 Final Thoughts

This problem elegantly mixes heap-based greedy algorithms with queue management to enforce constraints. Great practice for:

• Greedy thinking
• Priority queues
• Sliding window/cooldown mechanics