767. Reorganize String

可以利用358. Rearrange String k Distance Apart
O(n) time O(n) space
把原字符串按字母频重组成一个字符串，再用两个指针，一个从头，一个从中间（+1），往结果字符串里插，一定可以保证没有重复字母出现
aaaaabbcc ==> ababacaca
这里需要证明：

1. 每次append的两个字符不一样
   因为每个字符频数最多只能是(n + 1) / 2，所以第二个字符一定是从中间的下一个开始取，所以一定不一样
2. 上一次append的第二个字符和本次append的第一个字符不一样
   反证法，如果两个字符一样，说明该字符频数至少是(n + 1) / 2，但是因为该字符频数最多只能排到第二，所以一定还有一个字符频数至少是(n + 1) / 2，这样两个字符频数和就超过n了，所以两个字符一定不一样

class Solution {
public:
    string reorganizeString(string S) {
        int n = S.length();
        int f[26] = {0}; // 很牛逼的编码方式，f[i] = freq * 100 + i，避免使用pair的麻烦
        iota(f, f + 26, 0);
        for (char c : S) {
            f[c - 'a'] += 100;
        }
        sort(f, f + 26, greater<>());
        if (f[0] / 100 > (n + 1) / 2) return ""; // 如果某个字符过多，直接返回空串
        string s;
        for (int i = 0; i < 26; ++i) {
            s.append(f[i] / 100, 'a' + f[i] % 100); // 按频数由大到小重组字符串
        }
        string res;
        for (int i = 0; i < (n + 1) / 2; ++i) {
            res += s[i];
            int j = i + (n + 1) / 2;
            if (j < n) {
                res += s[j];
            }
        }
        return res;
    }
};

heap O(n) time O(1) space
这里需要证明：

1. 每次push的两个字符不一样
   heap每个元素都是针对一个字符的，所以一定不一样
2. 上一次push的第二个字符和本次push的第一个字符不一样
   因为每次push的第一个字符的频数一定大于等于push的第二个字符的频数，所以本次push的第一个字符不可能比上次push的第一个字符优先级更高

class Solution {
public:
    string reorganizeString(string S) {
        int n = S.length();
        int f[26] = {0};
        for (char c : S) {
            f[c - 'a'] += 100;
        }
        priority_queue<int, vector<int>> q;
        for (int i = 0; i < 26; ++i) {
            if (f[i] / 100 > (n + 1) / 2) return "";
            if (f[i]) {
                q.push(f[i] + i);
            }
        }
        string res;
        while (q.size() > 1) {
            int f1 = q.top(); q.pop();
            int f2 = q.top(); q.pop();
            res += ('a' + f1 % 100); f1 -= 100;
            res += ('a' + f2 % 100); f2 -= 100;
            if (f1 >= 100) {
                q.push(f1);
            }
            if (f2 >= 100) {
                q.push(f2);
            }
        }
        if (!q.empty()) {
            res += ('a' + q.top() % 100);
        }
        return res;
    }
};