重构字符串，使得两相邻的字符不同

题目链接：767. 重构字符串 - 力扣（LeetCode） (leetcode-cn.com)

参考文章：(17条消息) JAVA程序设计：重构字符串（LeetCode：767）_信仰.的博客-CSDN博客

思路一：排序

我们按照字符出现的频率进行排序，这样相同的字符此时是连续出现的，我们可以每隔一个字符空位插入一个字符，但是有一种特殊情况是出现次数最多的字符可能出现了（n+1）/2次，此时有可能前两个字符会出现相同的情况，为了避免这种情况，我们要使出现次数最多的字母排在最后，因此我们选择从小到大排序，问题解决了

public String reorganizeString(String S) {
    int len=S.length();
    int[] nums=new int[26];
    // 例如S="aabbccc",则nums={200,200,300}
    for(char c : S.toCharArray()) {
        nums[c-'a']+=100;
    }
    // 例如S="aabbccc",则nums={200,201,302}
    for(int i=0;i<26;i++) {
        nums[i]+=i;
    }
    Arrays.parallelSort(nums);
    int t=1;
    char[] ans=new char[len];
    for(int num : nums) {
        // 获取字符的数量
        int ct=num/100;
        // 获取具体字符
        char ch=(char)('a'+(num%100));
        // 如果字符数超过一半，则不满足
        if(ct>(len+1)/2) {
            return "";
        }
        // 间隔插入字符
        for(int i=0;i<ct;i++) {
            if(t>=len) {
                t=0;
            }
            ans[t]=ch;
            t+=2;
        }
    }
    return new String(ans);
}

思路二：优先队列

我们考虑每次插入的字符是出现次数最多的字符，可以这么做的原因在于，只有当一个字符出现的次数超过 (N+1) / 2 的情况下，这个问题才无解。只要初试情况下这个条件满足，每次都输出剩余出现次数最多的字符就可以将这个条件一直保持下去

class node{
    // 字符数量
    int count;
    // 具体字符
    char letter;
    public node(int count,char letter) {
        this.count=count;
        this.letter=letter;
    }
}

public String reorganizeString(String S) {
    int len=S.length();
    int[] nums=new int[26];
    for(char c : S.toCharArray()) {
        nums[c-'a']++;
    }
    // 创建优先队列，按字符数量大小倒排，再按字符大小正排
    PriorityQueue<node> q=new PriorityQueue<node>(
        (a,b)->a.count==b.count?a.letter-b.letter:b.count-a.count);
    for(int i=0;i<26;i++) {
        if(nums[i]==0) {
            continue;
        }
        // 如果字符数超过一半，则不满足
        if(nums[i]>(len+1)/2) {
            return "";
        }
        q.add(new node(nums[i],(char)('a'+i)));
    }
    StringBuilder ans=new StringBuilder();
    // 两两添加字符
    while(q.size()>=2) {
        // 获取优先级最高的两个字符
        node a1=q.poll();
        node a2=q.poll();
        // 依次排序
        ans.append(a1.letter);
        ans.append(a2.letter);
        // 使用后，数量减一再放回优先队列中
        if(--a1.count>0) {
            q.add(a1);
        }
        if(--a2.count>0) {
            q.add(a2);
        }
    }
    // 如果队列中还存在字符
    if(q.size()>0) {
        ans.append(q.poll().letter);
    }
    return new String(ans);
}