767. Reorganize String

[LLancelot]

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"

Example 2:

Input: S = "aaab"
Output: ""

思路：

• 这道题的解法有多种，Heap, PriorityQueue, Greedy 等等。我的解法是，先把出现次数最多的字符ch找到，再把ch全部放在result中的第0, 2, 4, 6...等位置上，保证剩下的待插入字符可以安排在第1, 3, 5 ... 的位置。index 初始化为0，步长为2，即 index += 2。
• 插入字符的过程可以理解成：先将偶数下标的位置填满，再把剩下的奇数填满。用index记录插入字符在result中的下标，类似循环队列，当index超过result的size时，将index = 1，保证可以填满整个result.
• 关于记录每个字符出现的次数，这里用int[] hash数组（长度26，对应每个英文字符）来统计。

代码：

class Solution {
    public String reorganizeString(String S) {
        int[] hash = new int[26]; // hash.length = 26
        for(int i = 0; i < S.length(); i++) {
            hash[S.charAt(i) - 'a']++;
        }
        int max = 0, letter = 0;
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] > max) {
                max = hash[i];
                letter = i;
            }
        }
        if (max > (S.length() + 1) / 2) {
            return "";
        }
        char[] res = new char[S.length()];
        int idx = 0;

        // 先把最高频字母安排在0,2,4,6....等位置上
        while (hash[letter] > 0) {
            res[idx] = (char) (letter + 'a');
            idx += 2;
            hash[letter]--; 
        }

        // 对剩下的字母，分别对其安排在1,3,5,7的位置上
        for (int i = 0; i < hash.length; i++) {
            while (hash[i] > 0) {
                if (idx >= res.length) { // idx重置
                    idx = 1;
                }
                res[idx] = (char) (i + 'a');
                idx += 2;
                hash[i]--;
            }
        }
        return String.valueOf(res);
    }
}