Rearrange String k Distance Apart

Problem Statement

Given a string s and an integer k, the task is to rearrange the characters in s such that identical characters are separated by at least a distance of k. If rearranging the string to meet this condition is not feasible, the function should return an empty string "". This problem involves analyzing the frequency of each character in the string and strategically placing them apart based on the specified distance k.

Examples

Example 1

Input:

s = "aabbcc", k = 3

Output:

"abcabc"

Explanation:

The same letters are at least a distance of 3 from each other.

Example 2

Input:

s = "aaabc", k = 3

Output:

""

Explanation:

It is not possible to rearrange the string.

Example 3

Input:

s = "aaadbbcc", k = 2

Output:

"abacabcd"

Explanation:

The same letters are at least a distance of 2 from each other.

Constraints

• 1 <= s.length <= 3 * 105
• s consists of only lowercase English letters.
• 0 <= k <= s.length

Approach and Intuition

Understanding how to tackle this problem can be grasped better when we break down the examples provided:

Example Analysis

1. Example 1:

   • Input: s = "aabbcc", k = 3
   • Output: "abcabc"
   • Explanation: Each character (a, b, c) appears twice. Given the condition k = 3, after placing the first occurrence of each character, the second occurrence can be placed right after completing one full cycle of unique characters, satisfying the minimum distance condition between identical characters.

2. Example 2:

   • Input: s = "aaabc", k = 3
   • Output: ""
   • Explanation: Here, the frequency of a is 3. With k = 3, and the total number of characters only 5, it is impossible to position three as such that each is separated by at least 2 other characters.

3. Example 3:

   • Input: s = "aaadbbcc", k = 2
   • Output: "abacabcd"
   • Explanation: In this scenario, a appears three times, but with k = 2, it is feasible to position the as such that each is separated by at least one other different character, which is achieved in the output.

From these examples, the key steps to approach this problem include:

1. Count the frequency of each character in the string.
2. Use a priority queue to manage the order of insertion based on the highest frequency characters.
3. Plan the placement of characters to maintain at least k distance by filling temporary blocked positions which get unblocked as we place more characters.
4. If at any point it's not possible to place an element due to reaching an impossible state (i.e., needing to place a character but not having enough distance from its last placement), conclude that it's not possible to rearrange the string as desired.

This type of problem is akin to task scheduling with cooling periods, where you must ensure certain tasks (or characters, in this context) are not executed (or placed) consecutively without a defined break or gap according to the condition provided (k in this problem).

Solutions

class Solution {
public:
    string shuffleString(string s, int k) {
        unordered_map<char, int> charCount;
        int highestFreq = 0;
    
        // Calculate character frequencies and determine the highest frequency
        for (char ch : s) {
            charCount[ch]++;
            highestFreq = max(highestFreq, charCount[ch]);
        }
            
        unordered_set<char> mostFrequentChars;
        unordered_set<char> nextMostFrequentChars;
            
        // Identify characters with the highest and next highest frequencies
        for (auto charFreq : charCount) {
            if (charFreq.second == highestFreq) {
                mostFrequentChars.insert(charFreq.first);
            } else if (charFreq.second == highestFreq - 1) {
                nextMostFrequentChars.insert(charFreq.first);
            }
        }
    
        // Create as many segments as the highest frequency
        string parts[highestFreq];
    
        // Populate each segment with characters with highest and second highest frequency
        for (int i = 0; i < highestFreq; i++) {
            for (char ch: mostFrequentChars) {
                parts[i] += ch;
            }
            if (i < highestFreq - 1) {
                for (char ch: nextMostFrequentChars) {
                    parts[i] += ch;
                }
            }
        }
    
        int partIndex = 0;
        // Distribute remaining characters across available parts
        for (auto charFreq : charCount) {
            char currentChar = charFreq.first;
            if (mostFrequentChars.count(currentChar) || nextMostFrequentChars.count(currentChar)) {
                continue;
            }
                
            for (int count = charFreq.second; count > 0; count--) {
                parts[partIndex] += currentChar;
                partIndex = (partIndex + 1) % (highestFreq - 1);
            }
        }
    
        // Ensure every part has at least k characters
        for (int i = 0; i < highestFreq - 1; i++) {
            if (parts[i].length() < k) {
                return "";
            }
        }
            
        string result;
        // Concatenate all the parts
        for (string part : parts) {
            result += part;
        }
            
        return result;
    }
};