358 Rearrange String k Distance Apart

1. Question

Given a non-empty stringsand 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 1:
1
s = "aabbcc", k = 3
2
3
Result: "abcabc"
4
5
The same letters are at least distance 3 from each other.
Copied!
Example 2:
1
s = "aaabc", k = 3
2
3
Answer: ""
4
5
It is not possible to rearrange the string.
Copied!
Example 3:
1
s = "aaadbbcc", k = 2
2
3
Answer: "abacabcd"
4
5
Another possible answer is: "abcabcda"
6
7
The same letters are at least distance 2 from each other.
Copied!

2. Implementation

(1) Heap
1
class Solution {
2
public String rearrangeString(String s, int k) {
3
if (k <= 1) {
4
return s;
5
}
6
7
int[] count = new int[256];
8
for (char c : s.toCharArray()) {
9
++count[c];
10
}
11
12
PriorityQueue<CharInfo> maxHeap = new PriorityQueue<>();
13
14
for (int i = 0; i < 256; i++) {
15
if (count[i] != 0) {
16
maxHeap.add(new CharInfo((char)i, count[i]));
17
}
18
}
19
20
Queue<CharInfo> buffer = new LinkedList<>();
21
StringBuilder res = new StringBuilder();
22
23
while (!maxHeap.isEmpty()) {
24
CharInfo curChar = maxHeap.remove();
25
res.append(curChar.val);
26
--curChar.freq;
27
buffer.add(curChar);
28
29
if (buffer.size() == k) {
30
curChar = buffer.remove();
31
if (curChar.freq > 0) {
32
maxHeap.add(curChar);
33
}
34
}
35
}
36
return res.length() == s.length() ? res.toString() : "";
37
}
38
39
class CharInfo implements Comparable<CharInfo> {
40
char val;
41
int freq;
42
43
public CharInfo(char val, int freq) {
44
this.val = val;
45
this.freq = freq;
46
}
47
48
public int compareTo(CharInfo that) {
49
return that.freq - this.freq;
50
}
51
}
52
}
Copied!

3. Time & Space Complexity

Heap: 时间复杂度O(nlog26) => O(n), 在这题heap存储的元素为26,因为所有字符都是lowercase, 空间复杂度O(n)