767. Reorganize String

題目

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: ""
      

Note:

• S

  will consist of lowercase letters and have length in range

  [1, 500]

  .

思路

該題目類型屬于排序題，我認為這個歸類不是太準确，應該歸到字元串處理這一類。題目要求将字元串中的字元重新排列，要求兩兩之間不能有相同字元，并輸出其中一種結果，如果不存在上述情況則輸出空字元串。

代碼

class Solution {
    public String reorganizeString(String S) {
        int N = S.length();
        int[] cnt = new int[];//count ASCII(256)
        char mc = 'a';//most frequent char(default 'a')
        //Frequency statistics
        for(char c:S.toCharArray())
        {
            cnt[c]++;
            mc = (cnt[c]>cnt[mc])?c:mc;//most frequent char
        }
        //return ""
        if((N-cnt[mc])<(cnt[mc]-))
            return "";
        //return one possible case
        StringBuilder[] sb = new StringBuilder[cnt[mc]];
        for(int i=;i<cnt[mc];i++)
        {
            sb[i] = new StringBuilder();
            sb[i].append(mc);
        }
        int k = ;
        //Loop interpolation   
        for(char c ='a';c<='z';c++)// defult in a~z
        {
            while(cnt[c]>&&c!=mc)
            {
                sb[k++].append(c);
                cnt[c]--;
                k%=cnt[mc];//loop
            }
        }
        for(int i=;i<cnt[mc];i++)
            sb[].append(sb[i]);
        return sb[].toString();
    }
}