767. Reorganize String

Link

Solution

How it works:

for example : aaabbbcdd

a_a_a_ _ _ _ , (input 'a', index difference is 1)

aba_a_a_ b_ b (input 'b', index difference is 1)

abaca_b_b (input 'c', index difference is 1)

abacadbdb (input 'd', index difference is 1)

 public String reorganizeString(String S) {
        int letterIndex = 0, mostFrequency = 0;
        int[] count = new int[26];
        for(int i = 0; i < S.length(); i++){
            count[S.charAt(i) - 'a'] ++;
            if(mostFrequency <= count[S.charAt(i) - 'a']){
                mostFrequency = count[S.charAt(i) - 'a'];
                letterIndex = S.charAt(i) - 'a';
            }
        }
        
        char[] charArray = new char[S.length()];
        int idx = 0;
        
        while(count[letterIndex] != 0){          
            if(idx >= charArray.length) return "";
            
            charArray[idx] = (char) (letterIndex + 'a');
            idx += 2;
            count[letterIndex]--;
        }
        
        for(int i = 0; i < 26; i++){
            while(count[i] != 0){
                if(idx >= charArray.length) idx = 1;
                charArray[idx] = (char) (i + 'a');
                idx += 2;
                count[i]--;
            }
        }
        return new String(charArray);
    }