767. Reorganize String

這個解法我真的是驚呆了 , 厲害

首先就是統計出現最多的字母, 看這個字母的2 n-1是不是大於S.size()

是的話就代表同樣的字母太多了

我比較納悶的是, 到底怎麼排比較好

首先先排字母出現最多次的, 然後從0開始放, 每次都跳兩個

當跳到i 等於S.size()或是 S.size() + 1的時候, 已經是尾端了, 所以讓i從1繼續開始間隔跳

這個作法簡單卻優美, 還真的想不到

class Solution {
  public:
    string reorganizeString(string S) {
        vector<int> count(26);
        int mostFreq = 0;
        int i = 0;
        for (char c : S) {
            int num = c - 'a';
            count[num]++;
            if (count[num] > count[mostFreq]) {
                mostFreq = num;
            }
        }
        if (2 * count[mostFreq] - 1 > S.size())
            return "";
        while (count[mostFreq]) {
            S[i] = ('a' + mostFreq);
            i += 2;
            count[mostFreq]--;
        }
        for (int j = 0; j < 26; j++) {
            while (count[j]) {
                if (i >= S.size())
                    i = 1;
                S[i] = ('a' + j);
                count[j]--;
                i += 2;
            }
        }
        return S;
    }
};