题目
给你一个非空的字符串 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() : "";
}
}
评论区