767. 重構字符串
給定一個字符串S，檢查是否能重新排布其中的字母，使得兩相鄰的字符不同。
若可行，輸出任意可行的結果。若不可行，返回空字符串。
示例 1:
輸入: S = “aab”
輸出: “aba”
示例 2:
輸入: S = “aaab”
輸出: “”
注意:
S 只包含小寫字母并且長度在[1, 500]區間內。
解題思路
根據相鄰字符串的特征，我們可以推出，如果某個字母出現的次數大于整個字符串長度的一半的話，那么無論如何我們都不能避免相鄰的重復字符串。
- 因此我們可以先判斷出現次數最多的字符串的長度
- 將出現次數最多的字符串填充至偶數下標中，如果不能填滿偶數下標，則讓其他字符串來湊，總之就是先填滿偶數下標的，再填奇數下標的
代碼
class Solution {public String reorganizeString(String s) {int n=s.length();int[] cnt=new int[26];int max=0;for(int i=0;i<s.length();i++){cnt[s.charAt(i)-'a']++;}for(int i=0;i<26;i++){if(cnt[i]>cnt[max])max=i;}int half=(int)Math.ceil((double)n/2.0);if(cnt[max]>half)return ""; char[] cur=new char[n];int idx=0;for(;idx<n&&cnt[max]-->0;idx+=2)cur[idx]=(char)(max+'a');StringBuilder sb=new StringBuilder();for(int i=0;i<26;i++){for(int j=0;j<cnt[i];j++,idx+=2){if(idx>=n)idx=1;cur[idx]=(char)(i+'a');} }return new String(cur);}}
