Untitled

import java.util.*;

public class RearrangeStringKDistance {
    public String rearrangeString(String s, int k) {
        if (k == 0) return s; // No restriction on distance

        // Step 1: Count frequency of each character
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        // Step 2: Use a max heap to prioritize the most frequent characters
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                maxHeap.add(new int[]{i, freq[i]});
            }
        }

        Queue<int[]> waitQueue = new LinkedList<>(); // Queue to ensure k-distance constraint
        StringBuilder result = new StringBuilder();

        // Step 3: Process the characters from the heap
        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll(); // Most frequent available character
            result.append((char) (curr[0] + 'a'));
            curr[1]--; // Reduce frequency

            // Add the character to the wait queue so it can be used after k positions
            waitQueue.add(curr);
            if (waitQueue.size() >= k) {
                int[] front = waitQueue.poll();
                if (front[1] > 0) {
                    maxHeap.add(front); // Push back into heap once it's valid to reuse
                }
            }
        }

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

    public static void main(String[] args) {
        RearrangeStringKDistance obj = new RearrangeStringKDistance();
        System.out.println(obj.rearrangeString("aabbcc", 3));  // Output: "abcabc"
        System.out.println(obj.rearrangeString("aaabc", 3));   // Output: ""
        System.out.println(obj.rearrangeString("aaadbbcc", 2)); // Output: "abacabcd"
    }
}