358. Rearrange String k Distance Apart (Hard)

Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1:

str = "aabbcc", k = 3

Result: "abcabc"

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

Example 2:

str = "aaabc", k = 3 

Answer: ""

It is not possible to rearrange the string.

Example 3:

str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

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

Solution 1: Hash Table, Heap, Greedy 385ms

这道题给了我们一个字符串str，和一个整数k，让我们对字符串str重新排序，使得其中相同的字符之间的距离不小于k，这道题的难度标为Hard，看来不是省油的灯。的确，这道题的解法用到了哈希表，堆，和贪婪算法。这道题我最开始想的算法没有通过OJ的大集合超时了，下面的方法是参考网上大神的解法，发现十分的巧妙。我们需要一个哈希表来建立字符和其出现次数之间的映射，然后需要一个堆来保存这每一堆映射，按照出现次数来排序。然后如果堆不为空我们就开始循环，我们找出k和str长度之间的较小值，然后从0遍历到这个较小值，对于每个遍历到的值，如果此时堆为空了，说明此位置没法填入字符了，返回空字符串，否则我们从堆顶取出一对映射，然后把字母加入结果res中，此时映射的个数减1，如果减1后的个数仍大于0，则我们将此映射加入临时集合v中，同时str的个数len减1，遍历完一次，我们把临时集合中的映射对由加入堆中，参见代码如下：

class Solution {
public:
    string rearrangeString(string str, int k) {
        if (k == 0) return str;

        unordered_map<char, int> m;
        for (auto& c:str) ++m[c];

        priority_queue<pair<int,char>> q;
        for (auto& a:m) q.push({a.second, a.first});

        int len = str.size();
        string res;

        while (!q.empty()) {
            vector<pair<int,char>> v;
            int cnt = min(k,len);

            for (int i = 0; i < cnt; ++i) {
                if (q.empty()) return "";
                auto t = q.top(); q.pop();
                res += t.second;
                if (--t.first > 0) v.push_back(t);
                --len;
            }
            for (auto& a:v) q.push(a);
        }

        return res;
    }
};

Solution 2: Hash Table, Greedy 12ms

Idea:

1. Count how many occurrences of each character: a:4, b:4, c:3, d:2, e:1
2. put the most 2 characters (ab) at least k apart first as reference point: abXXabXXabXXab (X is empty position)

3. then fill the gap with all other numbers from most frequency to least frequency like filling out a rotated array: 2.1 fill with c first: abCXabCXabCXab 2.2 fill with d then: abcDabcDabcXab 2.3 fill with e: abcdEabcdabcEab // Here, first E is actually put last, second E is put first, because we are filling gaps in rotated manner. Note, it doesn't matter if it runs out of empty space, just insert E after abcd anyway, it won't break anything; 2.4 fill with f: abcdeabcdfabceab //A valid solution is generated.

4. Finally, how to determine if there is a solution: It's easy: At step 2, if you can't fill all the all empty positions with remaining characters after step 1, there is no solution.

Note:

pos = (pos+1)% max(a.first, max_cnt-1):

• 对最多出现的字母来说，每个str_arr的entry都会被填满 %max_count
• 对别的字母来说，先要把前max_cnt个entry填满，所以 %(max_cnt-1)

class Solution {
public:
    string rearrangeString(string str, int k) {
        int char_map[26] = {0};
        for (auto c: str) ++char_map[c-'a'];
        multimap<int,char,greater<int>> count_map;
        for (int i = 0; i < 26; ++i) {
            if (char_map[i]) count_map.emplace(char_map[i], i+'a');
        }
        int max_cnt = count_map.begin()->first, pos = 0;
        string str_arr[max_cnt];
        for (auto& a: count_map) {
            for (int i = 0; i < a.first; ++i) {
                str_arr[pos].push_back(a.second);
                pos = (pos+1)% max(a.first, max_cnt-1);
            }
        }
        string res;
        for (int i = 0; i < max_cnt-1; ++i) {
            if (str_arr[i].size() < k) return "";
            else res += str_arr[i];
        }
        res += str_arr[max_cnt-1];
        return res;
    }
};