Rearrange String k Distance Apart

🎯

Rearrange String k Distance Apart

hardHEAPAmazonGoogleFacebook

Imagine you are organizing a concert and want to schedule songs so that the same artist's songs are spaced out by at least k songs to keep the audience engaged.

💡 This problem involves rearranging characters in a string so that no two identical characters are too close. Beginners often struggle because it requires managing character frequencies and enforcing spacing constraints simultaneously, which is not straightforward with simple sorting or greedy methods alone.

📋

Problem Statement

Given a string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. If it is not possible to rearrange the string to satisfy this condition, return an empty string. Otherwise, return any valid rearrangement.

1 ≤ s.length ≤ 10^5s consists of lowercase English letters1 ≤ k ≤ s.length

💡

Example

Input"s = \"aabbcc\", k = 3"

Output"abcabc"

Characters 'a', 'b', and 'c' are spaced at least 3 apart in the rearranged string.

Input"s = \"aaabc\", k = 3"

Output""

It is impossible to rearrange 'aaabc' so that the same characters are at least 3 apart.

Input"s = \"aaadbbcc\", k = 2"

Output"abacabcd"

One valid rearrangement where each same character is at least 2 apart.

• k = 0 → original string returned as is
• All characters are unique → any permutation is valid
• String with one character repeated many times and k > 1 → likely impossible
• String length less than k → impossible to rearrange if duplicates exist

⚠️

Common Mistakes

Not enforcing the k-distance constraint properly

Characters appear too close, violating problem requirements

✅ Use a cooldown queue or sliding window to delay reuse of characters

Using a normal queue instead of a priority queue for character selection

May pick less frequent characters first, resulting in no valid rearrangement

✅ Use a max heap to always pick the character with highest remaining frequency

Not handling the case k=0 separately

Unnecessary complexity or incorrect output

✅ Return original string immediately if k=0

Forgetting to check if the final string length matches original

Returning partial or invalid rearrangement

✅ Compare lengths and return empty string if mismatch

Sorting the heap inefficiently in JavaScript

Slower performance due to repeated sorting

✅ Implement a proper priority queue or minimize sorting calls

🧠

Brute Force (Backtracking)

💡 This approach tries all possible permutations to find a valid rearrangement. It is extremely slow but helps understand the problem's constraints and why naive methods fail.

Intuition

Try placing characters one by one ensuring the k-distance constraint is met by checking the last positions of each character. Backtrack if stuck.

Algorithm

1. Count frequency of each character.
2. Use backtracking to build the string one character at a time.
3. At each step, choose a character that hasn't been used in the last k positions.
4. If no character can be placed, backtrack and try another character.

💡 The main difficulty is enforcing the k-distance constraint while exploring permutations, which leads to exponential complexity.

</>

Code

from collections import Counter

def rearrangeString(s, k):
    if k == 0:
        return s
    freq = Counter(s)
    n = len(s)
    res = [''] * n
    last_pos = {c: -k for c in freq}

    def backtrack(i):
        if i == n:
            return True
        for c in freq:
            if freq[c] > 0 and i - last_pos[c] >= k:
                res[i] = c
                freq[c] -= 1
                last_pos[c] = i
                if backtrack(i + 1):
                    return True
                freq[c] += 1
                last_pos[c] = i - k
        return False

    if backtrack(0):
        return ''.join(res)
    else:
        return ""

# Driver code
if __name__ == '__main__':
    print(rearrangeString("aabbcc", 3))  # Expected: a valid rearrangement like 'abcabc'
    print(rearrangeString("aaabc", 3))  # Expected: '' (impossible)

Line Notes

if k == 0:If no spacing needed, original string is valid

freq = Counter(s)Count character frequencies to know availability

n = len(s)Store length of string for iteration

res = [''] * nInitialize result list to build rearranged string

last_pos = {c: -k for c in freq}Initialize last positions to allow placement at start

for c in freq:Try all characters to place at current position

if freq[c] > 0 and i - last_pos[c] >= k:Enforce k-distance constraint before placing

res[i] = cPlace character c at position i

freq[c] -= 1Use one occurrence of character c

last_pos[c] = iUpdate last position of character c

if backtrack(i + 1):Recursively try to build rest of string

freq[c] += 1Backtrack: restore frequency if placement fails

last_pos[c] = i - kBacktrack last position to previous state

return FalseReturn false if no character can be placed at position i

if backtrack(0):Start backtracking from position 0

return ''.join(res)Return the successfully built string

return ""Return empty string if no valid rearrangement

import java.util.*;

public class RearrangeStringKDistance {
    public static String rearrangeString(String s, int k) {
        if (k == 0) return s;
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
        int n = s.length();
        char[] res = new char[n];
        Map<Character, Integer> lastPos = new HashMap<>();
        for (char c : freq.keySet()) lastPos.put(c, -k);

        return backtrack(0, n, freq, lastPos, res, k) ? new String(res) : "";
    }

    private static boolean backtrack(int i, int n, Map<Character, Integer> freq, Map<Character, Integer> lastPos, char[] res, int k) {
        if (i == n) return true;
        for (char c : freq.keySet()) {
            if (freq.get(c) > 0 && i - lastPos.get(c) >= k) {
                res[i] = c;
                freq.put(c, freq.get(c) - 1);
                lastPos.put(c, i);
                if (backtrack(i + 1, n, freq, lastPos, res, k)) return true;
                freq.put(c, freq.get(c) + 1);
                lastPos.put(c, i - k);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(rearrangeString("aabbcc", 3)); // Expected: valid rearrangement
        System.out.println(rearrangeString("aaabc", 3)); // Expected: ""
    }
}

Line Notes

if (k == 0) return s;No rearrangement needed if k=0

for (char c : s.toCharArray())Count frequencies of characters

int n = s.length();Store length of string for iteration

char[] res = new char[n];Initialize result array to build rearranged string

for (char c : freq.keySet()) lastPos.put(c, -k);Initialize last positions to allow placement at start

for (char c : freq.keySet()) {Try all characters to place at current position

if (freq.get(c) > 0 && i - lastPos.get(c) >= k)Check if character c can be placed at position i

res[i] = c;Place character c at position i

freq.put(c, freq.get(c) - 1);Use one occurrence of character c

lastPos.put(c, i);Update last position of character c

if (backtrack(i + 1, n, freq, lastPos, res, k))Recursively build the string

freq.put(c, freq.get(c) + 1);Backtrack frequency if placement fails

lastPos.put(c, i - k);Backtrack last position to previous state

return false;Return false if no character can be placed at position i

if (i == n) return true;Return true if all positions filled

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

bool backtrack(int i, int n, unordered_map<char, int>& freq, unordered_map<char, int>& lastPos, vector<char>& res, int k) {
    if (i == n) return true;
    for (auto& p : freq) {
        char c = p.first;
        if (p.second > 0 && i - lastPos[c] >= k) {
            res[i] = c;
            freq[c]--;
            lastPos[c] = i;
            if (backtrack(i + 1, n, freq, lastPos, res, k)) return true;
            freq[c]++;
            lastPos[c] = i - k;
        }
    }
    return false;
}

string rearrangeString(string s, int k) {
    if (k == 0) return s;
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    int n = s.size();
    vector<char> res(n);
    unordered_map<char, int> lastPos;
    for (auto& p : freq) lastPos[p.first] = -k;
    if (backtrack(0, n, freq, lastPos, res, k))
        return string(res.begin(), res.end());
    else
        return "";
}

int main() {
    cout << rearrangeString("aabbcc", 3) << endl; // Expected: valid rearrangement
    cout << rearrangeString("aaabc", 3) << endl; // Expected: ""
    return 0;
}

Line Notes

if (k == 0) return s;No rearrangement needed if k=0

for (char c : s) freq[c]++;Count character frequencies

int n = s.size();Store length of string for iteration

vector<char> res(n);Initialize result vector to build rearranged string

for (auto& p : freq) lastPos[p.first] = -k;Initialize last positions for placement

for (auto& p : freq) {Try all characters to place at current position

if (p.second > 0 && i - lastPos[c] >= k)Check if character c can be placed at position i

res[i] = c;Place character c at position i

freq[c]--;Use one occurrence of character c

lastPos[c] = i;Update last position of character c

if (backtrack(i + 1, n, freq, lastPos, res, k))Recursively build the string

freq[c]++;Backtrack frequency if placement fails

lastPos[c] = i - k;Backtrack last position to previous state

return false;Return false if no character can be placed at position i

if (i == n) return true;Return true if all positions filled

function rearrangeString(s, k) {
    if (k === 0) return s;
    const freq = new Map();
    for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
    const n = s.length;
    const res = new Array(n);
    const lastPos = new Map();
    for (const c of freq.keys()) lastPos.set(c, -k);

    function backtrack(i) {
        if (i === n) return true;
        for (const [c, count] of freq.entries()) {
            if (count > 0 && i - lastPos.get(c) >= k) {
                res[i] = c;
                freq.set(c, count - 1);
                lastPos.set(c, i);
                if (backtrack(i + 1)) return true;
                freq.set(c, count);
                lastPos.set(c, i - k);
            }
        }
        return false;
    }

    return backtrack(0) ? res.join('') : '';
}

// Driver code
console.log(rearrangeString("aabbcc", 3)); // Expected: valid rearrangement
console.log(rearrangeString("aaabc", 3)); // Expected: ''

Line Notes

if (k === 0) return s;No rearrangement needed if k=0

for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);Count character frequencies

const n = s.length;Store length of string for iteration

const res = new Array(n);Initialize result array to build rearranged string

for (const c of freq.keys()) lastPos.set(c, -k);Initialize last positions for placement

for (const [c, count] of freq.entries()) {Try all characters to place at current position

if (count > 0 && i - lastPos.get(c) >= k)Check if character c can be placed at position i

res[i] = c;Place character c at position i

freq.set(c, count - 1);Use one occurrence of character c

lastPos.set(c, i);Update last position of character c

if (backtrack(i + 1))Recursively build the string

freq.set(c, count);Backtrack frequency if placement fails

lastPos.set(c, i - k);Backtrack last position to previous state

return false;Return false if no character can be placed at position i

if (i === n) return true;Return true if all positions filled

⏱

Complexity

TimeO(n!)

SpaceO(n)

Backtracking tries all permutations, which is factorial in string length n, making it infeasible for large inputs.

💡 For n=10, this means over 3 million permutations to check, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem constraints and why more efficient methods are needed.

🧠

Greedy with Max Heap and Cooldown Queue

💡 This approach uses a max heap to always pick the character with the highest remaining frequency and a queue to enforce the k-distance cooldown, making it efficient and intuitive once understood.

Intuition

Always pick the most frequent character available, then wait k positions before reusing it, using a queue to track cooldown characters.

Algorithm

1. Count frequencies of characters.
2. Push all characters into a max heap based on frequency.
3. Pop the most frequent character and append it to the result.
4. Put the used character into a cooldown queue with the position it can be used again (i + k).
5. If the cooldown queue front is ready, push it back into the heap.
6. Repeat until heap is empty.
7. If the result length equals original string length, return result; else return empty string.

💡 The key is managing the cooldown queue to ensure characters are spaced at least k apart while always picking the most frequent available character.

</>

Code

from collections import Counter, deque
import heapq

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

    while max_heap or queue:
        time += 1
        if max_heap:
            count, char = heapq.heappop(max_heap)
            res.append(char)
            if -count > 1:
                queue.append((char, count + 1, time + k))  # decrement count and set next available time
        else:
            # idle time, no char available
            if queue and queue[0][2] > time:
                return ""

        if queue and queue[0][2] == time:
            c, cnt, _ = queue.popleft()
            heapq.heappush(max_heap, (cnt, c))

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

# Driver code
if __name__ == '__main__':
    print(rearrangeString("aabbcc", 3))  # Expected: valid rearrangement
    print(rearrangeString("aaabc", 3))  # Expected: ''

Line Notes

if k == 0:No rearrangement needed if k=0

freq = Counter(s)Count character frequencies to know availability

max_heap = [(-count, char) for char, count in freq.items()]Use negative counts for max heap in Python

heapq.heapify(max_heap)Transform list into a heap for efficient max extraction

queue = deque()Queue to hold characters in cooldown

res = []List to build the rearranged string

time = 0Simulate time steps for scheduling

while max_heap or queue:Continue until all characters are placed or impossible

time += 1Increment time step

if max_heap:Pick most frequent available character

count, char = heapq.heappop(max_heap)Pop character with highest frequency

res.append(char)Append chosen character to result

if -count > 1:If character still has remaining count

queue.append((char, count + 1, time + k))Add character to cooldown with updated count and available time

else:No character available to place

if queue and queue[0][2] > time:If cooldown not finished, no valid rearrangement

return ""Return empty string if impossible

if queue and queue[0][2] == time:Release character from cooldown when ready

c, cnt, _ = queue.popleft()Pop character from cooldown queue

heapq.heappush(max_heap, (cnt, c))Push character back to heap with updated count

return ''.join(res) if len(res) == len(s) else ""Return result if valid, else empty string

import java.util.*;

public class RearrangeStringKDistance {
    public static String rearrangeString(String s, int k) {
        if (k == 0) return s;
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            maxHeap.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        Queue<int[]> queue = new LinkedList<>(); // stores [char, count, availableTime]
        StringBuilder res = new StringBuilder();
        int time = 0;

        while (!maxHeap.isEmpty() || !queue.isEmpty()) {
            time++;
            if (!maxHeap.isEmpty()) {
                int[] curr = maxHeap.poll();
                res.append((char) curr[0]);
                if (curr[1] > 1) {
                    queue.offer(new int[]{curr[0], curr[1] - 1, time + k});
                }
            } else {
                if (!queue.isEmpty() && queue.peek()[2] > time) {
                    return "";
                }
            }
            if (!queue.isEmpty() && queue.peek()[2] == time) {
                maxHeap.offer(queue.poll());
            }
        }
        return res.length() == s.length() ? res.toString() : "";
    }

    public static void main(String[] args) {
        System.out.println(rearrangeString("aabbcc", 3)); // Expected: valid rearrangement
        System.out.println(rearrangeString("aaabc", 3)); // Expected: ""
    }
}

Line Notes

if (k == 0) return s;No rearrangement needed if k=0

for (char c : s.toCharArray())Count frequencies of characters

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);Max heap based on frequency

for (Map.Entry<Character, Integer> entry : freq.entrySet()) {Add all characters to max heap

Queue<int[]> queue = new LinkedList<>();Cooldown queue to hold characters temporarily

StringBuilder res = new StringBuilder();Build result string

int time = 0;Simulate time steps for scheduling

while (!maxHeap.isEmpty() || !queue.isEmpty()) {Continue until all characters placed or impossible

time++;Increment time step

if (!maxHeap.isEmpty()) {Pick most frequent character available

int[] curr = maxHeap.poll();Pop character with highest frequency

res.append((char) curr[0]);Append chosen character to result

if (curr[1] > 1) {If character still has remaining count

queue.offer(new int[]{curr[0], curr[1] - 1, time + k});Add character to cooldown with updated count and available time

} else {No character available to place

if (!queue.isEmpty() && queue.peek()[2] > time) {If cooldown not finished, no valid rearrangement

return "";Return empty string if impossible

if (!queue.isEmpty() && queue.peek()[2] == time) {Release character from cooldown when ready

maxHeap.offer(queue.poll());Push character back to heap with updated count

return res.length() == s.length() ? res.toString() : "";Return valid rearrangement or empty string

#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

string rearrangeString(string s, int k) {
    if (k == 0) return s;
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    auto cmp = [](pair<int, char>& a, pair<int, char>& b) { return a.first < b.first; };
    priority_queue<pair<int, char>, vector<pair<int, char>>, decltype(cmp)> maxHeap(cmp);
    for (auto& p : freq) maxHeap.push({p.second, p.first});
    queue<pair<char, pair<int, int>>> cooldown; // char, count, available_time
    string res;
    int time = 0;

    while (!maxHeap.empty() || !cooldown.empty()) {
        time++;
        if (!maxHeap.empty()) {
            auto curr = maxHeap.top(); maxHeap.pop();
            res.push_back(curr.second);
            if (curr.first > 1) {
                cooldown.push({curr.second, {curr.first - 1, time + k}});
            }
        } else {
            if (!cooldown.empty() && cooldown.front().second.second > time) {
                return "";
            }
        }
        if (!cooldown.empty() && cooldown.front().second.second == time) {
            auto front = cooldown.front(); cooldown.pop();
            maxHeap.push({front.second.first, front.first});
        }
    }
    return res.size() == s.size() ? res : "";
}

int main() {
    cout << rearrangeString("aabbcc", 3) << endl; // Expected: valid rearrangement
    cout << rearrangeString("aaabc", 3) << endl; // Expected: ""
    return 0;
}

Line Notes

if (k == 0) return s;No rearrangement needed if k=0

for (char c : s) freq[c]++;Count character frequencies

auto cmp = [](pair<int, char>& a, pair<int, char>& b) { return a.first < b.first; };Comparator for max heap by frequency

priority_queue<pair<int, char>, vector<pair<int, char>>, decltype(cmp)> maxHeap(cmp);Max heap based on frequency

for (auto& p : freq) maxHeap.push({p.second, p.first});Add all characters to max heap

queue<pair<char, pair<int, int>>> cooldown;Cooldown queue to hold characters temporarily

string res;Build result string

int time = 0;Simulate time steps for scheduling

while (!maxHeap.empty() || !cooldown.empty()) {Continue until all characters placed or impossible

time++;Increment time step

if (!maxHeap.empty()) {Pick most frequent character available

auto curr = maxHeap.top(); maxHeap.pop();Pop character with highest frequency

res.push_back(curr.second);Append chosen character to result

if (curr.first > 1) {If character still has remaining count

cooldown.push({curr.second, {curr.first - 1, time + k}});Add character to cooldown with updated count and available time

} else {No character available to place

if (!cooldown.empty() && cooldown.front().second.second > time) {If cooldown not finished, no valid rearrangement

return "";Return empty string if impossible

if (!cooldown.empty() && cooldown.front().second.second == time) {Release character from cooldown when ready

auto front = cooldown.front(); cooldown.pop();Pop character from cooldown queue

maxHeap.push({front.second.first, front.first});Push character back to heap with updated count

return res.size() == s.size() ? res : "";Return valid rearrangement or empty string

function rearrangeString(s, k) {
    if (k === 0) return s;
    const freq = new Map();
    for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
    const n = s.length;
    const res = [];
    const maxHeap = [];
    for (const [c, count] of freq.entries()) {
        maxHeap.push({char: c, count});
    }
    maxHeap.sort((a, b) => b.count - a.count);
    const queue = [];
    let time = 0;

    while (maxHeap.length > 0 || queue.length > 0) {
        time++;
        if (maxHeap.length > 0) {
            const curr = maxHeap.shift();
            res.push(curr.char);
            if (curr.count > 1) {
                queue.push({char: curr.char, count: curr.count - 1, availableTime: time + k});
            }
        } else {
            if (queue.length > 0 && queue[0].availableTime > time) {
                return "";
            }
        }
        if (queue.length > 0 && queue[0].availableTime === time) {
            maxHeap.push(queue.shift());
            maxHeap.sort((a, b) => b.count - a.count);
        }
    }
    return res.length === s.length ? res.join('') : '';
}

// Driver code
console.log(rearrangeString("aabbcc", 3)); // Expected: valid rearrangement
console.log(rearrangeString("aaabc", 3)); // Expected: ''

Line Notes

if (k === 0) return s;No rearrangement needed if k=0

for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);Count character frequencies

const n = s.length;Store length of string for iteration

const res = [];Build result array

const maxHeap = [];Array to simulate max heap

for (const [c, count] of freq.entries()) {Add all characters to max heap array

maxHeap.sort((a, b) => b.count - a.count);Sort again to maintain max heap order

const queue = [];Cooldown queue to hold characters temporarily

let time = 0;Simulate time steps for scheduling

while (maxHeap.length > 0 || queue.length > 0) {Continue until all characters placed or impossible

time++;Increment time step

if (maxHeap.length > 0) {Pick most frequent character available

const curr = maxHeap.shift();Pop character with highest frequency

res.push(curr.char);Append chosen character to result

if (curr.count > 1) {If character still has remaining count

queue.push({char: curr.char, count: curr.count - 1, availableTime: time + k});Add character to cooldown with updated count and available time

} else {No character available to place

if (queue.length > 0 && queue[0].availableTime > time) {If cooldown not finished, no valid rearrangement

return "";Return empty string if impossible

if (queue.length > 0 && queue[0].availableTime === time) {Release character from cooldown when ready

maxHeap.push(queue.shift());Push character back to heap array

return res.length === s.length ? res.join('') : '';Return valid rearrangement or empty string

⏱

Complexity

TimeO(n log m)

SpaceO(m)

n is string length, m is number of unique chars. Each character is pushed and popped from heap and queue at most once, heap operations cost log m.

💡 For n=100000 and m=26, this approach is efficient and practical for interviews.

Interview Verdict: Accepted

This is the optimal and commonly accepted solution for this problem in interviews.

🧠

Greedy with Max Heap and Fixed Size Queue (Sliding Window)

💡 This approach is a variation of the previous one but uses a fixed-size queue to hold the last k used characters, simplifying cooldown management.

Intuition

Use a max heap to pick the most frequent character and a queue of size k to hold recently used characters, releasing them after k steps.

Algorithm

1. Count frequencies of characters.
2. Push all characters into a max heap based on frequency.
3. Pop the most frequent character and append it to the result.
4. Add the used character to a queue.
5. If the queue size reaches k, pop from queue and if that character still has remaining count, push it back to the heap.
6. Repeat until heap is empty.
7. If the result length equals original string length, return result; else return empty string.

💡 The fixed-size queue acts as a sliding window enforcing the k-distance constraint by delaying reuse of characters.

</>

Code

from collections import Counter, deque
import heapq

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

    while max_heap:
        count, char = heapq.heappop(max_heap)
        res.append(char)
        queue.append((char, count + 1))  # decrement count
        if len(queue) < k:
            continue
        front_char, front_count = queue.popleft()
        if front_count < 0:
            heapq.heappush(max_heap, (front_count, front_char))

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

# Driver code
if __name__ == '__main__':
    print(rearrangeString("aabbcc", 3))  # Expected: valid rearrangement
    print(rearrangeString("aaabc", 3))  # Expected: ''

Line Notes

if k == 0:No rearrangement needed if k=0

freq = Counter(s)Count character frequencies

max_heap = [(-count, char) for char, count in freq.items()]Build max heap with negative counts

heapq.heapify(max_heap)Transform list into a heap

queue = deque()Queue to hold last k used characters

res = []Build result string

while max_heap:Process until no characters left

count, char = heapq.heappop(max_heap)Pop most frequent character

res.append(char)Append character to result

queue.append((char, count + 1))Add character with decremented count to queue

if len(queue) < k:Wait until queue size reaches k before releasing characters

front_char, front_count = queue.popleft()Pop oldest character from queue

if front_count < 0:If character still has remaining count, push back to heap

heapq.heappush(max_heap, (front_count, front_char))Push character back to heap

return ''.join(res) if len(res) == len(s) else ""Return valid rearrangement or empty string

import java.util.*;

public class RearrangeStringKDistance {
    public static String rearrangeString(String s, int k) {
        if (k == 0) return s;
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            maxHeap.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        Queue<int[]> queue = new LinkedList<>();
        StringBuilder res = new StringBuilder();

        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll();
            res.append((char) curr[0]);
            queue.offer(new int[]{curr[0], curr[1] - 1});
            if (queue.size() < k) continue;
            int[] front = queue.poll();
            if (front[1] > 0) maxHeap.offer(front);
        }
        return res.length() == s.length() ? res.toString() : "";
    }

    public static void main(String[] args) {
        System.out.println(rearrangeString("aabbcc", 3)); // Expected: valid rearrangement
        System.out.println(rearrangeString("aaabc", 3)); // Expected: ""
    }
}

Line Notes

if (k == 0) return s;No rearrangement needed if k=0

for (char c : s.toCharArray())Count frequencies of characters

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);Max heap by frequency

for (Map.Entry<Character, Integer> entry : freq.entrySet()) {Add all characters to max heap

Queue<int[]> queue = new LinkedList<>();Queue to hold last k used characters

StringBuilder res = new StringBuilder();Build result string

while (!maxHeap.isEmpty()) {Process until no characters left

int[] curr = maxHeap.poll();Pop most frequent character

res.append((char) curr[0]);Append character to result

queue.offer(new int[]{curr[0], curr[1] - 1});Add character with decremented count to queue

if (queue.size() < k) continue;Wait until queue size reaches k before releasing characters

int[] front = queue.poll();Pop oldest character from queue

if (front[1] > 0) maxHeap.offer(front);Push back if character still has remaining count

return res.length() == s.length() ? res.toString() : "";Return valid rearrangement or empty string

#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

string rearrangeString(string s, int k) {
    if (k == 0) return s;
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    auto cmp = [](pair<int, char>& a, pair<int, char>& b) { return a.first < b.first; };
    priority_queue<pair<int, char>, vector<pair<int, char>>, decltype(cmp)> maxHeap(cmp);
    for (auto& p : freq) maxHeap.push({p.second, p.first});
    queue<pair<char, int>> q;
    string res;

    while (!maxHeap.empty()) {
        auto curr = maxHeap.top(); maxHeap.pop();
        res.push_back(curr.second);
        q.push({curr.second, curr.first - 1});
        if ((int)q.size() < k) continue;
        auto front = q.front(); q.pop();
        if (front.second > 0) maxHeap.push({front.second, front.first});
    }
    return res.size() == s.size() ? res : "";
}

int main() {
    cout << rearrangeString("aabbcc", 3) << endl; // Expected: valid rearrangement
    cout << rearrangeString("aaabc", 3) << endl; // Expected: ""
    return 0;
}

Line Notes

if (k == 0) return s;No rearrangement needed if k=0

for (char c : s) freq[c]++;Count character frequencies

auto cmp = [](pair<int, char>& a, pair<int, char>& b) { return a.first < b.first; };Comparator for max heap by frequency

priority_queue<pair<int, char>, vector<pair<int, char>>, decltype(cmp)> maxHeap(cmp);Max heap by frequency

for (auto& p : freq) maxHeap.push({p.second, p.first});Add all characters to max heap

queue<pair<char, int>> q;Queue to hold last k used characters

string res;Build result string

while (!maxHeap.empty()) {Process until no characters left

auto curr = maxHeap.top(); maxHeap.pop();Pop most frequent character

res.push_back(curr.second);Append character to result

q.push({curr.second, curr.first - 1});Add character with decremented count to queue

if ((int)q.size() < k) continue;Wait until queue size reaches k before releasing characters

auto front = q.front(); q.pop();Pop oldest character from queue

if (front.second > 0) maxHeap.push({front.second, front.first});Push back if character still has remaining count

return res.size() == s.size() ? res : "";Return valid rearrangement or empty string

function rearrangeString(s, k) {
    if (k === 0) return s;
    const freq = new Map();
    for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
    const maxHeap = [];
    for (const [c, count] of freq.entries()) {
        maxHeap.push({char: c, count});
    }
    maxHeap.sort((a, b) => b.count - a.count);
    const queue = [];
    const res = [];

    while (maxHeap.length > 0) {
        const curr = maxHeap.shift();
        res.push(curr.char);
        queue.push({char: curr.char, count: curr.count - 1});
        if (queue.length < k) continue;
        const front = queue.shift();
        if (front.count > 0) {
            maxHeap.push(front);
            maxHeap.sort((a, b) => b.count - a.count);
        }
    }
    return res.length === s.length ? res.join('') : '';
}

// Driver code
console.log(rearrangeString("aabbcc", 3)); // Expected: valid rearrangement
console.log(rearrangeString("aaabc", 3)); // Expected: ''

Line Notes

if (k === 0) return s;No rearrangement needed if k=0

for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);Count character frequencies

const maxHeap = [];Array to simulate max heap

for (const [c, count] of freq.entries()) {Add all characters to max heap array

maxHeap.sort((a, b) => b.count - a.count);Sort again to maintain max heap order

const queue = [];Queue to hold last k used characters

const res = [];Build result array

while (maxHeap.length > 0) {Process until no characters left

const curr = maxHeap.shift();Pop most frequent character

res.push(curr.char);Append character to result

queue.push({char: curr.char, count: curr.count - 1});Add character with decremented count to queue

if (queue.length < k) continue;Wait until queue size reaches k before releasing characters

const front = queue.shift();Pop oldest character from queue

if (front.count > 0)If character still has remaining count

maxHeap.push(front);Push back to heap array

return res.length === s.length ? res.join('') : '';Return valid rearrangement or empty string

⏱

Complexity

TimeO(n log m)

SpaceO(m)

Similar to previous approach, heap operations dominate complexity, with m unique chars and n total length.

💡 This approach is efficient and often simpler to implement than the cooldown queue variant.

Interview Verdict: Accepted

This approach is optimal and a good alternative to the cooldown queue method.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the greedy max heap with cooldown queue approach for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n!)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Greedy with Max Heap and Cooldown Queue	O(n log m)	O(m)	No	Yes	Code this approach
3. Greedy with Max Heap and Fixed Size Queue	O(n log m)	O(m)	No	Yes	Alternative to approach 2, also acceptable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints, especially the meaning of k-distance.Step 2: Describe the brute force backtracking approach to show understanding of the problem complexity.Step 3: Introduce the greedy max heap with cooldown queue approach as the optimal solution.Step 4: Write clean, production-quality code for the heap-based approach.Step 5: Test with edge cases and explain time and space complexity.

Time Allocation

Clarify: 5min → Approach: 10min → Code: 15min → Test & Explain: 5min. Total ~35min

What the Interviewer Tests

The interviewer tests your ability to handle frequency-based scheduling with constraints, your knowledge of heaps and queues, and your skill in optimizing brute force solutions.

Common Follow-ups

• What if k=0? → Return original string immediately.
• Can you optimize space? → Use in-place structures or reduce queue size.
• What if characters are Unicode? → Use appropriate data structures for frequency.
• How to handle very large strings? → The heap approach scales well.

💡 These follow-ups test your understanding of edge cases, optimization, and adaptability to variations.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to rearrange or schedule tasks/characters with spacing or cooldown constraints, especially when frequency matters.

Signature Phrases

'rearrange string so that same characters are at least k distance apart''task scheduler with cooldown period k'

NOT This Pattern When

Problems that only require sorting or simple greedy without cooldown constraints

Similar Problems

Task Scheduler - scheduling tasks with cooldownsReorganize String - rearranging characters to avoid adjacent duplicatesMinimum Interval to Finish Tasks - interval scheduling with constraints

Practice

1. You are given an array of integers where you can perform operations to minimize the difference between the maximum and minimum elements. The operations allowed are doubling odd numbers once and halving even numbers multiple times. Which algorithmic approach guarantees finding the minimum possible deviation efficiently?

easy

A. Using a max-heap to iteratively reduce the maximum element while tracking the minimum

B. Brute force recursion trying all combinations of doubling and halving

C. Sorting the array and using a sliding window to find the minimal range

D. Dynamic programming to store states of all possible values after operations

Solution

1. Step 1: Understand problem constraints and operations

   The problem allows doubling odd numbers once and halving even numbers multiple times to minimize deviation.

2. Step 2: Identify approach that efficiently tracks max and min values

   Using a max-heap allows quick access to the current maximum, which can be reduced by halving, while tracking the minimum seen so far.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max-heap approach efficiently updates max and min values [OK]

Hint: Max-heap efficiently tracks max element for reduction [OK]

Common Mistakes:

• Thinking sorting + two pointers always works despite operations changing values
• Assuming brute force is feasible for large inputs
• Believing DP is needed despite no overlapping subproblems

2. Identify the bug in the following code snippet for computing maximum team performance:

import heapq

MOD = 10**9 + 7

def maxPerformance(n, speed, efficiency, k):
    engineers = sorted(zip(efficiency, speed), key=lambda x: -x[0])
    max_perf = 0
    speed_heap = []
    sum_speed = 0
    for eff, spd in engineers:
        heapq.heappush(speed_heap, spd)
        # Missing sum_speed update when popping
        if len(speed_heap) > k:
            heapq.heappop(speed_heap)
        sum_speed += spd
        max_perf = max(max_perf, sum_speed * eff)
    return max_perf % MOD

medium

A. Line where sum_speed is incremented by spd after pushing to heap

B. Line where engineers are sorted by efficiency descending

C. Line where heapq.heappop is called without updating sum_speed

D. Line where max_perf is updated with sum_speed * eff

Solution

1. Step 1: Identify heap pop operation

   When the heap size exceeds k, the smallest speed is popped but sum_speed is not decremented accordingly.

2. Step 2: Understand impact on sum_speed

   Not updating sum_speed causes it to include speeds no longer in the team, leading to incorrect performance calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   sum_speed must be updated when removing speed from heap [OK]

Hint: Check if sum_speed changes when popping from heap [OK]

Common Mistakes:

• Forgetting to update sum_speed on pop
• Sorting by wrong key
• Updating max_perf before sum_speed is correct

3. Consider the following buggy code snippet for sliding window median using a balanced sorted list. Which line contains the subtle bug that causes incorrect median results for even-sized windows?

medium

A. Line with 'return float(window[k // 2 - 1] + window[k // 2])'

B. Line with 'bisect.insort_left(window, nums[i])'

C. Line with 'idx = bisect.bisect_left(window, nums[i - k])'

D. Line with 'window = sorted(nums[:k])'

Solution

1. Step 1: Analyze median calculation for even k

   Median for even k is average of two middle elements, so sum must be divided by 2.

2. Step 2: Identify bug

   Line returning sum without division causes median to be twice the correct value.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing division by 2 in even median calculation [OK]

Hint: Even median requires averaging two middle elements [OK]

Common Mistakes:

• Forgetting to divide sum by 2 for even k median
• Incorrect index calculation for median
• Wrong removal or insertion causing imbalance

4. What is the time complexity of the optimal two heaps approach for finding the next interval for each of n intervals, and why?

medium

A. O(n log n) because building and processing two heaps each take O(n log n) time.

B. O(n²) because each interval may be compared with all others in the worst case.

C. O(n) because each interval is pushed and popped from heaps only once.

D. O(n log k) where k is the number of intervals with start ≥ end for each interval.

Solution

1. Step 1: Analyze heap operations

   Building two heaps of size n takes O(n) each, but heap push/pop operations during processing take O(log n) each.

2. Step 2: Count total operations

   Each interval is pushed and popped at most once from each heap, resulting in O(n log n) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap operations dominate complexity, confirming O(n log n) [OK]

Hint: Heap push/pop cost dominates, not linear scans [OK]

Common Mistakes:

• Assuming linear time due to single pass
• Confusing n and k in complexity
• Mistaking nested loops for heap operations

5. Suppose projects can be selected multiple times (reused) in the IPO problem. Which modification to the two-heaps algorithm correctly handles this scenario?

hard

A. Use a max-heap only and pick the top K profitable projects ignoring capital constraints

B. Do not remove projects from min-capital heap; instead, keep all projects always available

C. After selecting a project, reinsert it into the min-capital heap to allow reuse

D. After selecting a project, do not remove it from max-profit heap to allow repeated selection

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means projects remain available after selection, so they must be reinserted to be considered again.

2. Step 2: Modify algorithm accordingly

   After popping a project from min-capital heap and selecting it, reinsert it to allow future reuse; otherwise, it disappears from consideration.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Reinserting projects enables multiple selections [OK]

Hint: Reinsert projects after selection to allow reuse [OK]

Common Mistakes:

• Ignoring reinsertion, losing projects after first pick
• Keeping all projects always available breaks capital filtering
• Ignoring capital constraints when reusing projects