767. Reorganize String

重新组织给定字符串使得俩俩相邻的字符不相同，无法实现则返回空。是Rearrange String k Distance Apart的简化版，greedy的不断找剩余元素中最大的插入，因为如果不是选数目最多的放入最后让最大的剩下来就凑不足其它元素来间隔开它们。

/*
 * @lc app=leetcode id=767 lang=cpp
 *
 * [767] Reorganize String
 */

// @lc code=start
class Solution {
public:
    string reorganizeString(string S) {
        vector<int> freq(26, 0);
        for (const auto c : S) {
            ++freq[c - 'a'];
        }
        string res;
        for (int i = 0, last = -1; i < S.length(); ++i) {
            int mx = 0, mx_cnt = 0;
            bool found = false;
            for (int j = 0; j < 26; ++j) {
                if (freq[j] > mx_cnt && j != last) {
                    mx = j;
                    mx_cnt = freq[j];
                    found = true;
                }
            }   
            if (!found) return "";
            res += (mx + 'a');
            --freq[mx];
            last = mx;
        }
        return res;
    }
};
// @lc code=end