https://leetcode.com/contest/weekly-contest-68/problems/toeplitz-matrix/

class Solution {
public:
    string reorganizeString(string S) {
        map<char, int> m;
        map<char, int>::iterator it;
        string ans;
        for (int i = 0; i < S.length(); i++) {
            it = m.find(S.at(i));
            if (it != m.end()) {
                it->second++;
            } else {
                m.insert(make_pair(S.at(i), 1));
            }
        }
        int max;
        vector<pair<int, char>> tmp;
        for (it = m.begin(); it != m.end(); it++) {
            tmp.push_back(make_pair(it->second, it->first));
        }
        sort(tmp.begin(), tmp.end());

        int sum = 0;
        for (int i = 0; i < tmp.size() - 1; i++) {
            sum += tmp[i].first;
        }

        if (tmp[(tmp.size()-1)].first > sum + 1) {
            return ans;
        }

        for (int i = 0; i < tmp.size(); i++) {
            int pos = 0;
            char c = tmp[i].second;
            int count = tmp[i].first;
            while(count-- > 0) {
                int next = 2;
                if (pos >= ans.length())
                    next = 1;
                ans.insert(pos, 1, c);
                pos += next;
            }
        }
        cout << ans;
        return ans;
    }
};