358. Rearrange String k Distance Apart

• Difficulty: Hard

• Topics: Hash Table, Heap, Greedy

• Similar Questions:

  • Task Scheduler

  • Reorganize String

Problem:

Given a non-empty string s 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:

Input: s = "aabbcc", k = 3
Output: "abcabc" 
Explanation: The same letters are at least distance 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 distance 2 from each other.

Solutions:

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k <= 0) return s; // This special case if important
        if (s.length() == 0)    return s;

        int len = s.length();

        unordered_map<char, int> charCount;
        for (auto c : s) {
            ++charCount[c];
        }

        vector<char> chars;
        for (auto& entry : charCount) {
            chars.push_back(entry.first);
        }

        sort(chars.begin(), chars.end(), [charCount](char c1, char c2) {
           return charCount.at(c1) > charCount.at(c2); 
        });

        int maxVal = charCount[chars[0]];
        int maxCount = 0;
        for (int i = 0; i < chars.size() && charCount[chars[i]] == maxVal; ++i) ++maxCount;


        if (len < (k * (maxVal - 1) + maxCount)) return "";

        vector<string> matrix(maxVal - 1);
        int pos = 0;
        for (int i = maxCount; i < chars.size(); ++i) {
            for (int j = 0; j < charCount[chars[i]]; ++j) {
                matrix[pos%(maxVal - 1)].push_back(chars[i]);
                ++pos;
            }
        }

        string ret;
        string maxStr;
        for (int i = 0; i < maxCount; ++i) {
            maxStr.push_back(chars[i]);
        }

        for (int i = 0; i < maxVal - 1; ++i) {
            ret.append(maxStr);
            ret.append(matrix[i]);
        }
        ret.append(maxStr);
        return ret;
    }
};