【排序, 哈希表】K 距离间隔重排字符串

题目

358. K 距离间隔重排字符串

---

给你一个非空的字符串 s 和一个整数 k ，你要将这个字符串 s 中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离 至少 为 k 。如果无法做到，请返回一个空字符串 ""。

示例 1：

输入: s = "aabbcc", k = 3
输出: "abcabc" 
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。

示例 2:

输入: s = "aaabc", k = 3
输出: "" 
解释: 没有办法找到可能的重排结果。

示例 3:

输入: s = "aaadbbcc", k = 2
输出: "abacabcd"
解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

提示：

• 1 <= s.length <= 3 * 10^5
• s 仅由小写英文字母组成
• 0 <= k <= s.length

解题

方法一：哈希表 优先队列

思路

首先创建一个哈希表(freqs)统计每个字符出现的次数，然后维护一个按重复次数降序排序的优先队列(priQueue)/大顶堆并把 freqs 中的键值对全部入队。

创建一个StringBuilder(ans)用来构造字符串，再维护一个普通队列(queue)用来记录已经加入 ans 中的字符。

遍历取出 priQueue 队头元素：

• 当前元素表示的字符拼入 ans 中并把其计数减一。
• 把当前元素放入 queue 中表示该字符已加入 ans 中。
• 如果 queue 中元素个数为 k，说明 ans 中距离上一个「queue 的队头元素表示的字符」已经间隔了 k 个字符了，可以把「queue 的队头元素表示的字符」再拼入一次了，如果其计数还大于 1，就把 queue 的队头元素取出放入 priQueue 中等待下次拼入。
• priQueue 中没有元素即退出循环。

如果 ans 长度和 s 相同，说明字符串已经重新排列完成，返回 ans.toString() 即可。

否则说明还有些字符在 queue 中没有装入 priQueue ，有些字符无法间隔 k 个距离，返回 ""。

代码

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int n = s.length();
        if (n < k) return "";
        Map<Character, Integer> freqs = new HashMap<>();
        for (char ch : s.toCharArray()) {
            freqs.put(ch, freqs.getOrDefault(ch, 0) + 1);
        }
        Queue<Map.Entry<Character, Integer>> priQueue =
            new PriorityQueue<>((a, b) ->b.getValue() - a.getValue());
        priQueue.addAll(freqs.entrySet());
        StringBuilder ans = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
        while (!priQueue.isEmpty()) {
            Map.Entry<Character, Integer> curr = priQueue.poll();
            ans.append(curr.getKey());
            curr.setValue(curr.getValue() - 1);
            queue.offer(curr);
            if (queue.size() == k) {
                Map.Entry<Character, Integer> next = queue.poll();
                if (next.getValue() > 0) priQueue.offer(next);
            }
        }
        return ans.length() == n ? ans.toString() : "";
    }
}

优化

因为字符串中只含有小写字母，所以哈希表可以用数组来待代替。

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int n = s.length();
        if (n < k) return "";
        int[] counts = new int[26];
        for (char ch : s.toCharArray()) {
            counts[ch - 'a']++;
        }
        Queue<int[]> priQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0) {
                priQueue.offer(new int[]{i, counts[i]});
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        StringBuilder ans = new StringBuilder(n);
        while (!priQueue.isEmpty()) {
            int[] curr = priQueue.poll();
            ans.append((char) (curr[0] + 'a'));
            curr[1]--;
            queue.offer(curr);
            if (queue.size() == k) {
                int[] next = queue.poll();
                if (next[1] > 0) priQueue.offer(next);
            }
        }
        return ans.length() == n ? ans.toString() : "";
    }
}