LeetCode Problem 358

Difficulty: 🔴 Hard
Topics: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting

Solution

LeetCode 358 - Rearrange String k Distance Apart

Problem Understanding

The problem gives us a string s and an integer k. We must rearrange the characters in the string so that identical characters are separated by at least k positions.

The phrase "at least distance k" means that if the same character appears multiple times, the difference between their indices in the final string must be greater than or equal to k.

For example, if k = 3, then two 'a' characters cannot appear within two positions of each other. Valid placements would look like this:

a _ _ a

because the second 'a' is exactly 3 positions away from the first.

The input consists of:

• A string s containing only lowercase English letters
• An integer k

The output should be:

• A rearranged version of the string satisfying the distance requirement, or
• An empty string "" if no valid arrangement exists

The constraints are important:

• s.length can be as large as 3 * 10^5
• Only lowercase English letters appear
• k can range from 0 to len(s)

These constraints immediately tell us that brute force permutation generation is impossible. Even a mildly exponential algorithm would fail for large inputs.

The fact that there are only 26 lowercase letters is useful because frequency counting becomes very efficient.

Several edge cases are important:

• k = 0, where no restriction exists, meaning the original string is already valid
• Strings with one repeated character, such as "aaaa"
• Situations where one character appears too frequently to be spaced apart enough
• Very short strings
• Cases where multiple valid answers exist, because the problem accepts any valid arrangement

The key challenge is balancing character placement so that high frequency characters are spread apart properly.

Approaches

Brute Force Approach

A brute force solution would generate all possible permutations of the string and check whether each permutation satisfies the distance constraint.

For every permutation:

1. Traverse the string
2. Record the last seen index of each character
3. Verify that repeated characters are at least k apart

If a valid permutation is found, return it.

This approach is correct because it exhaustively checks every possible arrangement. If a valid arrangement exists, brute force will eventually discover it.

However, the number of permutations is factorial in the length of the string:

O(n!)

Even for strings of length 15 or 20, this becomes computationally infeasible. Since the problem allows lengths up to 300000, brute force is completely impractical.

Optimal Greedy + Max Heap Approach

The key insight is that the characters with the highest frequencies are the hardest to place.

Suppose we have:

aaabc

with k = 3.

The character 'a' appears 3 times, so it requires enough spacing between occurrences. If we do not place high frequency characters carefully, we may reach a point where no valid placement remains.

This suggests a greedy strategy:

• Always place the currently most frequent available character
• Temporarily prevent it from being reused for the next k positions

A max heap is perfect for selecting the character with the highest remaining frequency.

We also need a mechanism to enforce the cooldown period before a character can be reused. A queue works well for this:

• After using a character, place it into a cooldown queue
• Once k positions have passed, reinsert it into the heap if it still has remaining occurrences

This approach efficiently simulates the spacing constraint while greedily constructing a valid answer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * n)	O(n!)	Generates all permutations and validates each
Optimal	O(n log 26) = O(n)	O(26) = O(1)	Uses greedy scheduling with heap and cooldown queue

Algorithm Walkthrough

Optimal Greedy Heap Algorithm

1. Handle the trivial case where k <= 1.

If k is 0 or 1, every arrangement is automatically valid because identical characters are already at least one position apart. In this case, we can immediately return the original string. 2. Count the frequency of each character.

We use a hash map or frequency counter to determine how many times each character appears. This tells us which characters are most difficult to schedule. 3. Build a max heap using character frequencies.

Python's heapq is a min heap, so we store negative frequencies to simulate max heap behavior.

Each heap entry contains:

• Remaining frequency
• Character

The heap always gives us the character with the largest remaining count. 4. Create a cooldown queue.

When a character is used, it cannot be reused for the next k - 1 positions.

We store recently used characters in a queue containing:

• Updated remaining frequency
• Character
• The future index when it becomes available again

5. Repeatedly build the answer.

At each step:

• Remove the most frequent available character from the heap
• Append it to the result
• Decrease its remaining frequency
• Put it into cooldown if more occurrences remain

6. Release expired cooldown characters.

Before each placement, check whether any characters in the cooldown queue have waited long enough.

If their cooldown period has expired, push them back into the heap. 7. Detect impossible situations.

If the heap becomes empty before the result length reaches len(s), then no valid character can be placed next.

This means the arrangement is impossible, so return "". 8. Return the constructed string.

If we successfully place all characters, the result is guaranteed to satisfy the spacing requirement.

Why it works

The algorithm maintains an important invariant:

• No character becomes available again until at least k positions have passed since its last use.

The max heap greedily prioritizes characters with the highest remaining frequencies, which prevents difficult characters from accumulating until the end.

If the algorithm cannot continue because the heap is empty while unfinished characters still exist in cooldown, then no valid arrangement is possible. Every remaining character violates the distance requirement, so returning "" is correct.

Python Solution

from collections import Counter, deque
import heapq
from typing import Deque, List, Tuple

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

        frequency = Counter(s)

        max_heap: List[Tuple[int, str]] = []
        for char, count in frequency.items():
            heapq.heappush(max_heap, (-count, char))

        cooldown: Deque[Tuple[int, int, str]] = deque()
        result = []

        position = 0

        while max_heap or cooldown:
            while cooldown and cooldown[0][0] <= position:
                _, remaining_count, char = cooldown.popleft()
                heapq.heappush(max_heap, (remaining_count, char))

            if not max_heap:
                return ""

            remaining_count, char = heapq.heappop(max_heap)

            result.append(char)

            remaining_count += 1

            if remaining_count < 0:
                available_position = position + k
                cooldown.append(
                    (available_position, remaining_count, char)
                )

            position += 1

        return "".join(result)

The implementation begins with a quick optimization for k <= 1. In that situation, the original string already satisfies the requirement.

Next, Counter computes the frequency of every character. These frequencies are inserted into a max heap using negative counts because Python's heapq implements a min heap.

The cooldown queue stores characters that were recently used and are temporarily unavailable. Each entry tracks:

• The earliest position where the character can be reused
• The remaining frequency
• The character itself

The main loop repeatedly constructs the answer one character at a time.

Before selecting the next character, the algorithm releases any cooldown entries whose waiting period has expired. Those characters are pushed back into the heap and become eligible again.

If the heap becomes empty while construction is incomplete, the algorithm immediately returns "" because no valid continuation exists.

Otherwise, the most frequent available character is selected and appended to the result. Its frequency is decreased, and if additional copies remain, it enters cooldown until position + k.

Finally, the result list is joined into a string and returned.

Go Solution

package main

import (
	"container/heap"
)

type Item struct {
	count int
	char  byte
}

type MaxHeap []Item

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i].count > h[j].count
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Item))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

type CooldownItem struct {
	availablePos int
	count        int
	char         byte
}

func rearrangeString(s string, k int) string {
	if k <= 1 {
		return s
	}

	frequency := make(map[byte]int)

	for i := 0; i < len(s); i++ {
		frequency[s[i]]++
	}

	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)

	for char, count := range frequency {
		heap.Push(maxHeap, Item{
			count: count,
			char:  char,
		})
	}

	cooldown := []CooldownItem{}
	result := make([]byte, 0, len(s))

	position := 0

	for maxHeap.Len() > 0 || len(cooldown) > 0 {
		for len(cooldown) > 0 &&
			cooldown[0].availablePos <= position {

			item := cooldown[0]
			cooldown = cooldown[1:]

			heap.Push(maxHeap, Item{
				count: item.count,
				char:  item.char,
			})
		}

		if maxHeap.Len() == 0 {
			return ""
		}

		item := heap.Pop(maxHeap).(Item)

		result = append(result, item.char)

		item.count--

		if item.count > 0 {
			cooldown = append(cooldown, CooldownItem{
				availablePos: position + k,
				count:        item.count,
				char:         item.char,
			})
		}

		position++
	}

	return string(result)
}

The Go implementation follows the same logic as the Python solution but requires explicit heap implementation using the container/heap package.

Unlike Python, Go does not provide a built in priority queue, so we define a custom MaxHeap type implementing the heap interface methods.

The cooldown structure is implemented using a slice acting as a queue. Since only lowercase English letters exist, memory usage remains very small.

Go strings are immutable, so the result is built using a byte slice and converted to a string at the end.

Worked Examples

Example 1

s = "aabbcc"
k = 3

Initial frequencies:

Character	Count
a	2
b	2
c	2

Initial heap:

[(2,a), (2,b), (2,c)]

Step-by-step execution

Position	Heap Before	Chosen	Cooldown After	Result
0	a2,b2,c2	a	a available at 3	a
1	b2,c2	b	a@3,b@4	ab
2	c2	c	a@3,b@4,c@5	abc
3	a1	a	b@4,c@5	abca
4	b1	b	c@5	abcab
5	c1	c	empty	abcabc

Final answer:

"abcabc"

All repeated characters are exactly 3 positions apart.

Example 2

s = "aaabc"
k = 3

Frequencies:

Character	Count
a	3
b	1
c	1

Step-by-step execution

Position	Heap Before	Chosen	Cooldown	Result
0	a3,b1,c1	a	a@3	a
1	b1,c1	b	a@3	ab
2	c1	c	a@3	abc
3	a2	a	a@6	abca
4	empty	impossible	a@6	failure

At position 4, no character is available because 'a' is still cooling down.

Therefore, the answer is:

""

Example 3

s = "aaadbbcc"
k = 2

Frequencies:

Character	Count
a	3
b	2
c	2
d	1

Step-by-step execution

Position	Heap Before	Chosen	Cooldown	Result
0	a3,b2,c2,d1	a	a@2	a
1	b2,c2,d1	b	a@2,b@3	ab
2	a2,c2,d1	a	b@3,a@4	aba
3	b1,c2,d1	c	a@4,c@5	abac
4	a1,b1,d1	a	c@5	abaca
5	b1,c1,d1	b	empty	abacab
6	c1,d1	c	empty	abacabc
7	d1	d	empty	abacabcd

Final answer:

"abacabcd"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log 26) = O(n)	Each character enters and leaves the heap a constant number of times
Space	O(26) = O(1)	Heap, frequency map, and cooldown queue store at most 26 letters

The heap contains at most 26 lowercase English characters, so heap operations are effectively constant time.

Each character occurrence is processed once when added to the result and possibly once more when reinserted into the heap after cooldown. Therefore, the total runtime scales linearly with the string length.

The auxiliary space remains constant relative to input size because only lowercase English letters exist.

Test Cases

def is_valid(arranged: str, k: int) -> bool:
    positions = {}

    for i, ch in enumerate(arranged):
        if ch in positions and i - positions[ch] < k:
            return False
        positions[ch] = i

    return True

solver = Solution()

# Provided examples
result = solver.rearrangeString("aabbcc", 3)
assert result != "" and is_valid(result, 3)  # standard valid rearrangement

assert solver.rearrangeString("aaabc", 3) == ""  # impossible arrangement

result = solver.rearrangeString("aaadbbcc", 2)
assert result != "" and is_valid(result, 2)  # multiple valid answers possible

# k = 0 should return original string
assert solver.rearrangeString("abc", 0) == "abc"  # no restriction

# k = 1 also always valid
assert solver.rearrangeString("aaaa", 1) == "aaaa"  # adjacent allowed

# Single character
assert solver.rearrangeString("a", 5) == "a"  # trivial case

# Impossible due to high frequency
assert solver.rearrangeString("aaaaab", 2) == ""  # cannot separate enough

# Already valid
result = solver.rearrangeString("abcdef", 3)
assert result != "" and is_valid(result, 3)  # unique characters

# Large repeated pattern
result = solver.rearrangeString("aaabbbccc", 3)
assert result != "" and is_valid(result, 3)  # balanced frequencies

# Exact spacing possible
result = solver.rearrangeString("aabb", 2)
assert result != "" and is_valid(result, 2)  # exact alternation

# Large k equal to length
assert solver.rearrangeString("aa", 2) == ""  # impossible with max spacing

# Multiple valid outputs
result = solver.rearrangeString("aaabcdd", 2)
assert result != "" and is_valid(result, 2)  # flexible arrangement

Test	Why
"aabbcc", k=3	Standard valid scheduling case
"aaabc", k=3"	Detects impossible arrangement
"aaadbbcc", k=2"	Tests mixed frequencies
"abc", k=0"	Verifies no restriction behavior
"aaaa", k=1"	Adjacent duplicates allowed
"a", k=5"	Single character edge case
"aaaaab", k=2"	Dominant frequency impossible case
"abcdef", k=3"	All unique characters
"aaabbbccc", k=3"	Balanced repeated characters
"aabb", k=2"	Exact alternation spacing
"aa", k=2"	Maximum spacing impossible
"aaabcdd", k=2"	Multiple valid outputs

Edge Cases

Case 1: k = 0

When k is zero, there is no spacing restriction at all. A naive implementation might still run the full heap logic unnecessarily or even fail due to cooldown handling.

The implementation explicitly checks:

if k <= 1:
    return s

This guarantees immediate correctness and avoids unnecessary processing.

Case 2: One Character Appears Too Frequently

Consider:

s = "aaaaab"
k = 2

There are not enough other characters to separate all 'a' occurrences.

A buggy implementation might continue greedily until late failure or accidentally produce invalid spacing.

The heap-based approach correctly detects impossibility when the heap becomes empty while cooldown still contains blocked characters. At that point, no legal next character exists.

Case 3: Very Large k

Suppose:

s = "abc"
k = 10

Since all characters are unique, the arrangement is still valid even though k exceeds the string length.

Some incorrect solutions assume large k automatically makes the problem impossible.

The current implementation does not rely on such assumptions. It only enforces spacing between identical characters, so unique characters work naturally.

Case 4: All Characters Identical

Example:

s = "aaaa"
k = 2

Only one character type exists, so spacing is impossible unless the string length is one.

The algorithm handles this naturally:

• One 'a' is placed
• 'a' enters cooldown
• The heap becomes empty
• Construction fails immediately

This correctly returns "".