HardHash TableStringGreedySortingHeap (Priority Queue)Counting

Rearrange String k Distance Apart

1 approach, code in every language

You are given a string s and an integer k. Reorder the characters of s so that any two identical characters are separated by a distance of at least k positions.

If no such arrangement is possible, return an empty string. When k is 0 or 1 there is no spacing requirement, so the original string is already valid.

Example 1

Input: s = "aabbcc", k = 3

Output: "abcabc"

Each pair of identical letters ends up three positions apart, satisfying the distance requirement.

Example 2

Input: s = "aaabc", k = 3

Output: ""

There are three a's but only five slots, so at least two a's must land closer than three apart. It is impossible, so the answer is the empty string.

Constraints

1 <= s.length <= 3 * 10^5
s consists of only lowercase English letters.
0 <= k <= s.length

Max-Heap with Cooldown Queue

Always emit the most frequent available character, holding used characters in a cooldown queue of size k.

Loading animation…

Intuition

To keep identical characters far apart, we should always spend the character that has the most copies left, because it is the hardest one to place later. A max-heap keyed on remaining count gives us that character in logarithmic time. After emitting a character we cannot reuse it until k positions have passed, so we park it in a cooldown queue; only when the queue grows to length k does the front element become eligible to re-enter the heap. If the heap ever empties while characters are still waiting in cooldown, we could not place everyone with the required spacing, so the arrangement is impossible.

Algorithm walkthrough

1If k is 0 or 1 there is no spacing constraint, so return s unchanged.
2Count character frequencies and push each (count, character) pair into a max-heap.
3Pop the character with the largest remaining count, append it to the result, and decrement its count.
4Push the just-used character into a cooldown queue holding the last k picks.
5Once the queue reaches size k, remove its front element and, if it still has copies left, push it back onto the heap.
6When the heap is empty, return the result if it covers every character, otherwise return an empty string.

Implementation

import heapq
from collections import Counter, deque

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s
        counts = Counter(s)
        heap = [(-cnt, ch) for ch, cnt in counts.items()]
        heapq.heapify(heap)
        result = []
        queue = deque()
        while heap:
            cnt, ch = heapq.heappop(heap)
            result.append(ch)
            queue.append((cnt + 1, ch))
            if len(queue) < k:
                continue
            front_cnt, front_ch = queue.popleft()
            if front_cnt < 0:
                heapq.heappush(heap, (front_cnt, front_ch))
        return "".join(result) if len(result) == len(s) else ""

Time

O(N log A)

Space

O(N)

N is the string length and A the alphabet size (at most 26), so each of the N heap operations costs O(log A). The result buffer needs O(N) space plus an O(k) cooldown queue.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free