?LeetCode刷題實戰(zhàn)358：K 距離間隔重排字符串

Given a non-empty string s 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 "".

示例 1：

輸入: s = “aabbcc”, k = 3
輸出: “abcabc”
解釋: 相同的字母在新的字符串中間隔至少 3 個單位距離。

示例 2:

輸入: s = “aaabc”, k = 3
輸出: “”
解釋: 沒有辦法找到可能的重排結果。

示例 3:

輸入: s = “aaadbbcc”, k = 2
輸出: “abacabcd”
解釋: 相同的字母在新的字符串中間隔至少 2 個單位距離。

class Solution {
    public String rearrangeString(String str, int k) {
        if (k == 0) {
            return str;
        }
        // 1.構建單詞與頻率的映射
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch ,map.get(ch) + 1);
            } else {
                map.put(ch, 1);
            }
        }
        // 2.將所有出現的字母按照頻率排序
        PriorityQueue<Character> queue = new PriorityQueue<>((c1, c2) -> {
            if (map.get(c2).intValue() != map.get(c1).intValue()) {
                return map.get(c2) - map.get(c1);
            } else {
                // 如果頻率相同，按字典排序
                return c1.compareTo(c2);
            }
        });
        // 把字符放入隊列,頻率大的在前面
        for (char c: map.keySet()) {
            queue.offer(c);
        }
        // 試圖構建字符串
        StringBuilder sb = new StringBuilder();
        // 初始字符長度
        int len = str.length();
        // 3. 把字符按出現次數多的字符開始，把每一個字符插入到間隔中
        while (!queue.isEmpty()) {
            List<Character> tempChars = new ArrayList<>();
            // 得到較小的數（最后剩下的一截可能不夠K）
            int n = Math.min(k, len);
            // 從queue里取出TopN位數字，填充每一個間隔區(qū)間
            for (int i = 0; i < n; i++) {
                // 在個數為N的間隔區(qū)間里，剩下的不重復的字符串已經用完了,那么必然構造不出間隔為N的無重復字符串了，
                // 也就是在這個區(qū)間里必然有重復的字母，到這里就無法再繼續(xù)構造了
                if (queue.isEmpty()) {
                    return "";
                }
                // 取出這個字符
                char ch = queue.poll();
                sb.append(ch);
                // 取出這個字符，相應頻次要減1
                map.put(ch, map.get(ch) - 1);
                // 這個字符還有剩余,就加進來tempChars，重新放到queue里，進行下一次的遍歷
                if (map.get(ch) > 0) {
                    tempChars.add(ch);
                }
                // 已經取過了，字符長度減1
                len--;
            }

            // 4.每個字母減過一次了，把還有剩余次數的字母再次加入到queue里，繼續(xù)下一次的循環(huán)
            for (Character tempChar : tempChars) {
                queue.offer(tempChar);
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String res = solution.rearrangeString("aabbcc", 3);
        String res2 = solution.rearrangeString("aaabc", 3);
        String res3 = solution.rearrangeString("aaadbbcc", 2);
        System.out.println(res);
        System.out.println(res2);
        System.out.println(res3);
    }
}