解法：贪心

1.首先我们可以优先处理一批相同的字符。

2.优先处理的字符必须是出现次数最多多的字符。处理时，每隔一个格子就摆放一个该字符

因为出现次数最多的字符决定了我们这个字符串是否能重排：

假设字符串的长度是n，出现次数最多的字符的个数是x，则：

  • 如果n是偶数，当 x > n / 2 时，整个字符就不能重排了；
  • 如果n是奇数，当 x > ( n + 1 ) / 2 时，整个字符就不能重排了；

所以解题思路就是：

  1. 找出出现次数最大的字符
  2. 判断是否能重排
  3. 如果能重排，则重排字符串。重排方法就是：先处理出现次数最多多的字符，处理时，每隔一个格子就摆放一个该字符。处完后再处理其他字符。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
    string rearrangestring(string str) 
    {
        int n = str.size();
        // 1.找出出现次数最大的字符
        int cnt[26] = {0}; // cnt当哈希表统计各个字符出现次数
        char maxChar = 0; // 出现自出最多的那个字符
        int maxCount = 0; // 出现自出最多的那个字符的个数

        for(char ch : str)
        {
            int index = ch - 'a';
            if(++cnt[index] > maxCount)
            {
                // 更新最多的那个字符
                maxChar = ch;
                maxCount = cnt[index];
            }
        }
        // 2.判断是否能重排
        if(maxCount > (n + 1) / 2) 
        {
            return "";
        }
        else 
        {
            // 3.重排字符串
            string ret(n,'0');
            int i = 0; // 从 i 位置开始排

            // 先处理出现次数最多的那个字符（各一个位置就放一个）
            while(maxCount--)
            {
                ret[i] = maxChar;
                i += 2;
            }
            // 再处理剩余字符
            for(int j = 0; j < 26; j++)
            {
                if(cnt[j] && j + 'a' != maxChar)
                {
                    while(cnt[j]--)
                    {
                        if(i >= n) i = 1;
                        ret[i] = j + 'a';
                        i += 2;
                    }
                }
            }
            // 返回结果
            return ret;
        }
    }
};