Input: s = "aabbcc", k = 3

Output: "abcabc"

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

Input: s = "aaabc", k = 3

Output: ""

Explanation: It is not possible to rearrange the string.

Input: s = "aaadbbcc", k = 2

Output: "abacabcd"

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

bool cmp(pair<char, int> a, pair<char, int> b) {

    if (a.second != b.second) return a.second < b.second;

    return a.first < b.first;

}

class Solution {

public:

    string rearrangeString(string s, int k) {

        vector<pair<char, int>> map(, pair<char,int>('a',));

        for (int i = ; i < s.size(); i++) {

            int idx = s[i] - 'a';

            if (map[idx].second == ) {

                map[idx].first = s[i];

                map[idx].second = ;

            }

            else {

                map[idx].second++;

            }

        }

        sort(map.begin(), map.end(), cmp);

        //for(auto m : map) cout << m.first << m.second << endl;

        int idx = map.size() - ;

        int maxrep = map[idx].second;

        string ret = "";

        while (idx >=  && map[idx].second == maxrep) {

            string tmpstr = string(,map[idx].first);

            ret += tmpstr;

            idx--;

        }

        //cout << ret << endl;

        vector<string> retvec(map.back().second - , ret);

        int cnt = ;

        while (idx >=  && map[idx].second != ) {

            int tmp = idx;

            string tmpstr =string(, map[tmp].first);

            while (map[tmp].second != ) {

                retvec[cnt] += tmpstr;

                map[tmp].second--;

                cnt++;

                if(cnt >= retvec.size()) cnt = ;

            }

            idx--;

        }

        for (auto s : retvec) {

            if (s.size() < k) return "";

        }

        string finalret = "";

        for (auto s : retvec) finalret += s;

        finalret += ret;

        return finalret;

    }

};