/***  思路：如果s长度小于2，直接返回s，假设字符串s的长度为n。*        n为偶数，如果字符串中的某个字符数量超过 n/2 则肯定会存在相邻的字符。*        n为奇数，如果字符串中的某个字符的数量超过 （n+1）/ 2 ,肯定会存在相邻的字符。*        因为n为偶数时 (n+1)/2等于n/2，所以可以合并上面的两个情况。*        然后构建优先队列，优先队列是使用堆实现的，然后构建大顶堆。*        每次从优先队列取出出现次数最多的两个字符加入到结果中，*        然后将次数不为0 的字符再重新添加到优先队列中。* @auther start* @create 2024-01-12 14:34*/
public class L767 {public String reorganizeString(String s) {int len = s.length();if (len < 2) return s;int[] count = new int[26];int maxCount = 0;//统计字符出现次数for (int i = 0; i < len; i++) {char c = s.charAt(i);count[c - 'a']++;//出现最多的字符次数maxCount = Math.max(maxCount, count[c - 'a']);}//肯定有相邻字符出现的情况if (maxCount > (len + 1) / 2) {return "";}//构建优先队列PriorityQueue<Character> queue = new PriorityQueue<>(new Comparator<Character>() {@Override//构建大顶堆public int compare(Character o1, Character o2) {return count[o2 - 'a'] - count[o1 - 'a'];}});//添加字符到优先队列中for (char c = 'a'; c <= 'z'; c++) {if (count[c - 'a'] > 0) {queue.offer(c);}}StringBuffer res = new StringBuffer();while (queue.size() > 1) {//取出优先队列中的两个字符char c1 = queue.poll();char c2 = queue.poll();//添加到结果中res.append(c1);res.append(c2);int idx1 = c1 - 'a', idx2 = c2 - 'a';//这两个字符数量减一count[idx1]--;count[idx2]--;//判断这两个字符的数量是否大于1，大于1重新加入到优先队列中if (count[idx1] > 0)queue.offer(c1);if (count[idx2] > 0)queue.offer(c2);}//字符串长度为奇数的情况，取出最后一个字符if (queue.size() > 0) {res.append(queue.poll());}return res.toString();}
}