LeetCode -- 767. 重构字符串

设字符串s长度为len

s可以重构为相邻字符串不同时 有字符串中出现次数最多的字符 < (len + 1) >> 1

当满足上述条件时候，我们就能对其进行重构

重构法：先放置偶数位置，再放置奇数位置

c ++ 
class Solution {
public:
    string reorganizeString(string s) {
        vector<int> cnt(26, 0);
        int n = s.size();
        for(int i = 0; i < n; i ++ ) {
            cnt[s[i] - 'a'] ++ ;
        }

        int mx = 0, alp = 0, lim = (n + 1) >> 1;
        for(int i = 0; i < 26; i ++ ) {
            if(cnt[i] > mx) {
                mx = cnt[i];
                alp = i;
            }
        }

        if(mx > lim) return "";

        string res(n, ' ');
        int idx = 0;
        while(cnt[alp] -- > 0) {
            res[idx] = 'a' + alp;
            idx += 2;
        }

        for(int i = 0; i < 26; i ++ ) {
            while(cnt[i] -- > 0) {
                if(idx >= n) {
                    idx = 1;
                }
                res[idx] = 'a' + i;
                idx += 2;
            }
        }

        return res;
    }
};

解法二：利用桶（分组分类）思想

思路 1. 将相同的字符放入不同的桶中以保证其彼此不会相邻，因此桶的数目应等于字符串中最多的元素的数目； 2. 按贪心策略，优先填充数目最多的元素，对于每一种元素，循环在不同桶中进行填充，由于桶的个数等于字符串中最多的元素的数目，因此每个桶中不会出现相同的元素，填充完毕后将桶依次相连即为答案； 3. 若填充完毕后长度为1的桶（只可能出现在最后的位置）的数目多于1，将桶依次相连会使得这些长度为1的桶中的相同元素相邻，说明不存在相应的排列，返回""（这一情况即官解中说明的如果存在一个字母的出现次数大于(n+1)/2，其中n为字符串长度，则无法重新排布字母使得相邻的字母都不相同）。

c ++ 
class Solution {
public:
    string reorganizeString(string s) {
        vector<int> cnt(26);
        int n = s.size();
        for(int i = 0; i < n; i ++ ) {
            cnt[s[i] - 'a'] ++ ;
        }

        int mx = -1, pos = -1, lim = n + 1 >> 1;
        for(int i = 0; i < cnt.size(); i ++ ) {
            if(cnt[i] > mx) {
                mx = cnt[i];
                pos = i;
            }
        }
        if(mx > lim) return "";
        //初始化桶，将最多的元素放进去
        vector<string> buf(mx);
        for(int i = 0; i < cnt[pos]; i ++ ) {
            buf[i] += 'a' + pos;
        }
        cnt[pos] = 0;

        int idx = 0;
        for(int i = 0; i < 26; i ++ ) {
            for(int j = 0; j < cnt[i]; j ++ ) {
                buf[idx] += 'a' + i;
                idx = (idx + 1) % mx;
            }
        }

        string res;
        for(int i = 0; i < mx; i ++ ) {
            res += buf[i];
        }

        return res;
    }
};

python
class Solution:
    def reorganizeString(self, s: str) -> str:
        cnt, idx = Counter(s), 0
        bufnum = cnt.most_common(1)[0][1]
        if bufnum > (len(s) + 1) // 2:
            return ""
        buckets = [[] for _ in range(bufnum)]
        for c, num in cnt.most_common():
            for _ in range(num):
                buckets[idx].append(c)
                idx = (idx + 1) % bufnum
            
        return "".join(["".join(bucket) for bucket in buckets])