Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Rearrange String k Distance Apart

Rearrange String k Distance Apart

Master this topic with zero to advance depth.

Rearrange String k Distance Apart

Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".

Visual Representation

s = "aabbcc", k = 3 Frequency Count: a: 2, b: 2, c: 2 Step-by-Step Selection (k=3): Pos 0: Use 'a' (freq 2->1) | Wait: {a: wait 2} Pos 1: Use 'b' (freq 2->1) | Wait: {a: wait 1, b: wait 2} Pos 2: Use 'c' (freq 2->1) | Wait: {a: wait 0, b: wait 1, c: wait 2} Pos 3: 'a' is free! Use 'a'| Wait: {b: wait 0, c: wait 1, a: wait 2} ... Result: "abcabc"
Hard

Examples

Input: s = "aabbcc", k = 3
Output: "abcabc"
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Input: s = "aaabc", k = 3
Output: ""
Approach 1

Level I: Greedy with Max-Heap (Standard)

Intuition

We should always try to place the most frequent characters as early as possible. However, once a character is used, it cannot be used again for the next k-1 positions. Use a Max-Heap to track frequencies and a queue to manage the 'waitlist'.

Thought Process

  1. Count frequency of each character.
  2. Push char-frequency pairs into a Max-Heap.
  3. While heap is not empty:
    • Extract the character with the max frequency.
    • Append it to the result.
    • Decrement its frequency.
    • Add it to a 'waitlist' queue.
    • If the waitlist queue size reaches k, pop the character from the front and push it back into the heap (if its freq > 0).
⏱ O(N log A) where A is the alphabet size (26)💾 O(A)

Detailed Dry Run

s = "aaabc", k = 3

  1. Map: {a:3, b:1, c:1}, Heap: [a:3, b:1, c:1], Wait: []
  2. Step 1: Use 'a'. Result: "a", Heap: [b:1, c:1], Wait: [(a, 2)]
  3. Step 2: Use 'b'. Result: "ab", Heap: [c:1], Wait: [(a, 2), (b, 0)]
  4. Step 3: Use 'c'. Result: "abc", Heap: [], Wait: [(a, 2), (b, 0), (c, 0)]
  5. Wait size 3: Push 'a' back to heap. Heap: [a:2]
  6. Continue... (If result length != s length, return "")
java
import java.util.*;

public class Main {
    public static String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(counts.entrySet());

        StringBuilder res = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> waitlist = new LinkedList<>();

        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> current = maxHeap.poll();
            res.append(current.getKey());
            current.setValue(current.getValue() - 1);
            waitlist.offer(current);

            if (waitlist.size() < k) continue;
            
            Map.Entry<Character, Integer> front = waitlist.poll();
            if (front.getValue() > 0) maxHeap.offer(front);
        }

        return res.length() == s.length() ? res.toString() : "";
    }

    public static void main(String[] args) {
        System.out.println(rearrangeString("aabbcc", 3));
    }
}
Approach 2

Level II: Greedy with Alphabet Array (O(N * 26))

Intuition

Instead of a Max-Heap, we can directly use a frequency array of size 26. At each position in the result string, we scan all 26 characters to find the one that: 1. Is allowed to be placed (distance since last use >= k). 2. Has the maximum remaining frequency.

⏱ O(N * A) where A = 26💾 O(A)

Detailed Dry Run

s = "aabbcc", k = 3

  1. Freqs: {a:2, b:2, c:2}, LastPos: {a:-inf, b:-inf, c:-inf}
  2. Pos 0: 'a' is valid and max freq. Res: "a", Freqs: {a:1...}, LastPos: {a:0}
  3. Pos 1: 'a' invalid (1 < 3), 'b' is valid and max freq. Res: "ab"...
  4. Pos 3: 'a' becomes valid again (3-0 >= 3).
java
public class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int[] count = new int[26];
        int[] nextValid = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            int nextChar = findNextChar(count, nextValid, i);
            if (nextChar == -1) return "";
            count[nextChar]--;
            nextValid[nextChar] = i + k;
            sb.append((char)('a' + nextChar));
        }
        return sb.toString();
    }

    private int findNextChar(int[] count, int[] nextValid, int index) {
        int max = -1, res = -1;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0 && count[i] > max && index >= nextValid[i]) {
                max = count[i];
                res = i;
            }
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Modified Greedy with Max-Freq Limit Check)

Intuition

This approach uses a Max-Heap but adds a check to see if it's mathematically possible to rearrange. If the most frequent character appears more times than the available slots given distance k, it's impossible. We use a waitlist (cooling queue) to manage the distance k requirement.

⏱ O(N log A) where A = 26💾 O(A)

Detailed Dry Run

s = "aaabc", k = 3

  1. Freqs: {a:3, b:1, c:1}. Heap: [a:3, b:1, c:1]. Wait: []
  2. Pop 'a'. Res: "a". Freq: a:2. Wait: [a:2].
  3. Wait size < 3. Continue.
  4. If heap empty and res.length < s.length, return "".
java
import java.util.*;

public class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(counts.entrySet());

        StringBuilder res = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> waitlist = new LinkedList<>();

        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> current = maxHeap.poll();
            res.append(current.getKey());
            current.setValue(current.getValue() - 1);
            waitlist.offer(current);

            if (waitlist.size() < k) continue;
            
            Map.Entry<Character, Integer> front = waitlist.poll();
            if (front.getValue() > 0) maxHeap.offer(front);
        }

        return res.length() == s.length() ? res.toString() : "";
    }
}
← Previous QuestionMeeting Rooms II
Next Question →Find K Pairs with Smallest Sums