/*

     * 358. Rearrange String k Distance Apart

     * 2016-7-14 by Mingyang

     */

     public String rearrangeString(String str, int k) {

            int length = str.length();

            int[] count = new int[26];

            int[] valid = new int[26];

            for(int i=0;i<length;i++){

                count[str.charAt(i)-'a']++;

            }

            StringBuilder sb = new StringBuilder();

            for(int index = 0;index<length;index++){

                int candidatePos = findValidMax(count, valid, index);

                if( candidatePos == -1) return "";

                count[candidatePos]--;

                valid[candidatePos] = index+k;

                sb.append((char)('a'+candidatePos));

            }

            return sb.toString();

        }

       private int findValidMax(int[] count, int[] valid, int index){

           int max = Integer.MIN_VALUE;

           int candidatePos = -1;

           for(int i=0;i<count.length;i++){

               if(count[i]>0 && count[i]>max && index>=valid[i]){

                   max = count[i];

                   candidatePos = i;

               }

           }

           return candidatePos;

       }