358. Rearrange String k Distance Apart

Link

Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example:

str = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.

Solution

要將字母依照規則(間距>=k)的方式擺回去，那麼

• 每個字母的能使用的次數

• 每個字母下一個能擺放的位置

以上兩個資訊很重要。分別用兩個int array (count[], okIndex[])去紀錄。

然後設計一個function把能根據(count[], okIndex[], 目前擺到第幾個)，找到每次最適合擺放的字母。

     public String rearrangeString(String str, int k) {
        if(str == null || str.length() <= 1){
            return str;
        }
        int[] count = new int[26];
        int[] okIndex = new int[26];
        for(int i = 0; i < str.length(); i++){
            count[str.charAt(i) - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < str.length(); i++){
            int letter = findNextLetter(count, okIndex, i);
            if(letter == ' '){
                return ""; // we can't do it
            }
            sb.append((char)letter);
            //更新count跟okIndex
            count[letter - 'a']--;
            okIndex[letter - 'a'] = i + k;
        }
        return sb.toString();
    }
    public char findNextLetter(int[] count, int[] okIndex, int currentIndex){
        int maxCount = Integer.MIN_VALUE;
        char ret = ' ';
        for(int i = 0; i < count.length; i++) {
            //count > 0 然後 目前要排的位置比他OK的index大 然後count剩最多的字母
            if(count[i] > 0 && currentIndex >= okIndex[i] && count[i] > maxCount){
                maxCount = count[i];
                ret = (char)(i + 'a');
            }
        }
        return ret;
    }