题目描述
给你一个非空的字符串 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 * 105s 仅由小写英文字母组成0 <= k <= s.length
解法
方法一：贪心 + 哈希表 + 优先队列（大根堆）
我们用一个哈希表或数组 \(\textit{cnt}\) 来统计字符串中每个字母出现的次数，然后用一个大根堆 \(\textit{pq}\) 来存储每个字母及其出现次数。堆中的每个元素是一个二元组 \((v, c)\)，其中 \(v\) 和 \(c\) 分别表示字母出现的次数和字母本身。
在重排字符串时，我们每次从堆顶弹出一个元素 \((v, c)\)，将字母 \(c\) 添加到结果字符串中，并将 \((v-1, c)\) 放入一个队列 \(\textit{q}\) 中。当队列 \(\textit{q}\) 的长度达到 \(k\) 及以上时，弹出队首元素，若此时 \(v\) 大于 \(0\)，则将队首元素重新放入堆中。重复该过程，直到堆为空。
最后，我们判断结果字符串的长度是否与原字符串相等，若相等则返回结果字符串，否则返回空串。
时间复杂度为 \(O(n \log n)\)，其中 \(n\) 是字符串的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(|\Sigma|\) 是字符集的大小，本题中 \(|\Sigma| = 26\)。
相似题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def rearrangeString(self, s: str, k: int) -> str:
cnt = Counter(s)
pq = [(-v, c) for c, v in cnt.items()]
heapify(pq)
q = deque()
ans = []
while pq:
v, c = heappop(pq)
ans.append(c)
q.append((v + 1, c))
if len(q) >= k:
e = q.popleft()
if e[0]:
heappush(pq, e)
return "" if len(ans) < len(s) else "".join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public String rearrangeString(String s, int k) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) {
++cnt[c - 'a'];
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
for (int i = 0; i < cnt.length; ++i) {
if (cnt[i] > 0) {
pq.offer(new int[] {cnt[i], i});
}
}
Deque<int[]> q = new ArrayDeque<>();
StringBuilder ans = new StringBuilder();
while (!pq.isEmpty()) {
var p = pq.poll();
p[0] -= 1;
ans.append((char) ('a' + p[1]));
q.offerLast(p);
if (q.size() >= k) {
p = q.pollFirst();
if (p[0] > 0) {
pq.offer(p);
}
}
}
return ans.length() < s.length() ? "" : ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
public:
string rearrangeString(string s, int k) {
vector<int> cnt(26, 0);
for (char c : s) {
++cnt[c - 'a'];
}
priority_queue<pair<int, int>> pq;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
pq.emplace(cnt[i], i);
}
}
queue<pair<int, int>> q;
string ans;
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
p.first -= 1;
ans.push_back('a' + p.second);
q.push(p);
if (q.size() >= k) {
p = q.front();
q.pop();
if (p.first > 0) {
pq.push(p);
}
}
}
return ans.size() < s.size() ? "" : ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | func rearrangeString(s string, k int) string {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
pq := priorityqueue.NewWith(func(a, b any) int {
x := a.([2]int)
y := b.([2]int)
return y[0] - x[0]
})
for i := 0; i < 26; i++ {
if cnt[i] > 0 {
pq.Enqueue([2]int{cnt[i], i})
}
}
var q [][2]int
var ans strings.Builder
for pq.Size() > 0 {
p, _ := pq.Dequeue()
pair := p.([2]int)
pair[0]--
ans.WriteByte(byte('a' + pair[1]))
q = append(q, pair)
if len(q) >= k {
front := q[0]
q = q[1:]
if front[0] > 0 {
pq.Enqueue(front)
}
}
}
if ans.Len() < len(s) {
return ""
}
return ans.String()
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | export function rearrangeString(s: string, k: number): string {
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
const pq = new PriorityQueue<[number, number]>((a, b) => b[0] - a[0]);
for (let i = 0; i < 26; i++) {
if (cnt[i] > 0) {
pq.enqueue([cnt[i], i]);
}
}
const q: [number, number][] = [];
const ans: string[] = [];
while (!pq.isEmpty()) {
const [count, idx] = pq.dequeue()!;
const newCount = count - 1;
ans.push(String.fromCharCode('a'.charCodeAt(0) + idx));
q.push([newCount, idx]);
if (q.length >= k) {
const [frontCount, frontIdx] = q.shift()!;
if (frontCount > 0) {
pq.enqueue([frontCount, frontIdx]);
}
}
}
return ans.length < s.length ? '' : ans.join('');
}
|