358

358. Rearrange String k Distance Apart (Hard)

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 "".

 

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

Companies: Twitter, Google, Microsoft

Related Topics:
Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting

Similar Questions:

• Task Scheduler (Medium)
• Reorganize String (Medium)
• Construct String With Repeat Limit (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/rearrange-string-k-distance-apart
// Author: github.com/lzl124631x
// Time: O(ND) where D is the size of character set
// Space: O(D)
class Solution {
public:
    string rearrangeString(string s, int k) {
        int freq[26] = {}, maxFreq = 0, maxFreqCnt = 0, prev[26] = {[0 ... 25] = -1};
        for (char c : s) maxFreq = max(maxFreq, ++freq[c - 'a']);
        for (int i = 0; i < 26; ++i) maxFreqCnt += freq[i] == maxFreq;
        int other = s.size() - maxFreqCnt * maxFreq, segment = maxFreq - 1, gap = segment * (k - maxFreqCnt);
        if (gap > other) return ""; 
        string ans; 
        for (int i = 0; i < s.size(); ++i) {
            int pick = -1;
            for (int j = 0; j < 26; ++j) {
                if ((prev[j] == -1 || i - prev[j] >= k) && freq[j] > 0 && (pick == -1 || freq[j] > freq[pick])) {
                    pick = j;
                }
            }
            prev[pick] = i;
            freq[pick]--;
            ans += 'a' + pick;
        }
        return ans;
    }
};

Solution 2. Heap + Cooldown queue

// OJ: https://leetcode.com/problems/rearrange-string-k-distance-apart
// Author: github.com/lzl124631x
// Time: O(NlogD)
// Space: O(D)
class Solution {
public:
    string rearrangeString(string s, int k) {
        int freq[26] = {}, maxFreq = 0, maxFreqCnt = 0;
        for (char c : s) maxFreq = max(maxFreq, ++freq[c - 'a']);
        for (int i = 0; i < 26; ++i) maxFreqCnt += freq[i] == maxFreq;
        int other = s.size() - maxFreqCnt * maxFreq, segment = maxFreq - 1, gap = segment * (k - maxFreqCnt);
        if (gap > other) return ""; 
        auto cmp = [&](int a, int b) { return freq[a] < freq[b]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp); // a max heap of available characters
        queue<int> cd; // a cooldown queue with the index of the previous occurrence
        for (int i = 0; i < 26; ++i) {
            if (freq[i]) pq.push(i);
        }
        string ans; 
        for (int i = 0; i < s.size(); ++i) {
            if (cd.size() && cd.front() <= i - k) {
                pq.push(ans[cd.front()] - 'a');
                cd.pop();
            }
            int pick = pq.top();
            pq.pop();
            cd.push(i);
            freq[pick]--;
            ans += 'a' + pick;
        }
        return ans;
    }
};