Rearrange String K distance apart

XXX. Rearrange String k Distance Apart

Greedy

Priority Queue

Problem Statement:

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

Algorithm:

This problem is solved using a greedy approach combined with tracking the availability of characters:

1. Count the frequency of each character in the input string.
2. Iterate over the length of the string and, for each position:
   • Find the character with the highest frequency that can be placed at the current position (its next valid position must be <= the current index).
   • Place the character and update its next valid position based on k.
3. If no valid character is found for a position, return an empty string.
4. Continue until the string is completely rearranged.

Complexity:

Time Complexity: O(n * 26), where n is the length of the string. The inner loop iterates over a constant size (26 for lowercase English letters).
Space Complexity: O(26), for the frequency and next valid position arrays.

Java Implementation:

public class Solution {
    public String rearrangeString(String s, int k) {
        int count[] = new int[26]; // Frequency of each character
        int index[] = new int[26]; // Next valid position for each character

        // Count the frequency of each character
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }

        StringBuilder sb = new StringBuilder();

        // Build the rearranged string
        for (int i = 0; i < s.length(); i++) {
            int next = findNextLetter(i, count, index, k);
            if (next == -1) return ""; // No valid character found

            sb.append((char) (next + 'a'));
            count[next]--; // Decrease the frequency of the chosen character
        }

        return sb.toString();
    }

    // Find the next valid character to place at position i
    public int findNextLetter(int i, int[] count, int[] index, int k) {
        int max = 0;
        int candidate = -1;

        for (int j = 0; j < count.length; j++) {
            // Check if the character is valid and has the highest frequency
            if (count[j] > max && index[j] <= i) {
                max = count[j];
                candidate = j;
            }
        }

        // Update the next valid position for the chosen character
        if (candidate != -1) index[candidate] = i + k;

        return candidate;
    }
}