358 Rearrange String k Distance Apart

Search…

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)

347 Top K Frequent Elements

373 Find K Pairs with Smallest Sums

Last modified 2yr ago

Copy link

Contents

358. Rearrange String k Distance Apart

1. Question

2. Implementation

3. Time & Space Complexity

358. Rearrange String k Distance Apart​

1. Question

2. Implementation

3. Time & Space Complexity

358. Rearrange String k Distance Apart