Leetcode——767. Reorganize String

タイトルアドレス
https://leetcode.com/problems/reorganize-string/description/
タイトルの説明
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].
問題を解く構想.
1つの文字列を指定し、指定した文字列の文字の位置を移動して、返される文字列が隣接する2つの文字を同じにする必要があります.
考え方:

は、まず、与えられた文字列をintの配列に文字で格納し、配列の下に文字-aと表記するので、配列は同じ文字の個数を配列に格納する.

maxLengthを利用して配列中の要素の最大値、すなわち文字列の中で繰り返し現れる文字の最も多い文字の個数を得て、もしこの個数*2-1が文字列の長さより大きいならば、同じ文字が多すぎることを説明して、その他の文字はすでに同じ文字を

に分割することができません

文字列の文字を奇数偶数で新しいchar配列に配置します.同じ文字数が文字列の長さの半分未満の文字を奇数の下付き文字位置に、そうでない場合は偶数の下付き文字位置に置きます.なお、奇数位置が文字列長

より大きいか否かを判断する必要がある.
ACコード

class Solution {
    public String reorganizeString(String S) {
        int[] arr = new int[26];
        int lenght = S.length();
        if(S.length() == 1) return S;
        char[] ret = new char[lenght];
        int maxLength = 0;
        for(char a: S.toCharArray()) {
            if(maxLength < ++arr[a - 'a'])
                maxLength = arr[a - 'a'];
        }
        if(maxLength * 2 - 1 > S.length())
            return "";
        int odd = 0, even = 1;
        for(int i = 0; i < 26; i++) {

                while(arr[i] > 0 && arr[i] < lenght / 2 + 1 && even < lenght) {
                    ret[even] = (char)(i + 'a');
                    arr[i] --;
                    even += 2;
                }
                while(arr[i] > 0) {
                    ret[odd] = (char)(i + 'a');
                    arr[i] --;
                    odd += 2;
                }
        }

        return new String(ret);        
    }
}

に感謝
https://leetcode.com/problems/reorganize-string/discuss/113429/Java-O(N)-simple-solution