Description
Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".
Example 1:
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.
Example 2:
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.
Example 3:
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least a distance of 2 from each other.
Constraints:
1 <= s.length <= 3 * 105s consists of only lowercase English letters.0 <= k <= s.length
Solutions
Solution 1: Greedy + Hash Table + Priority Queue (Max Heap)
We use a hash table or array cnt to count the occurrences of each character in the string. Then, we use a max heap pq to store each character and its count. Each element in the heap is a tuple (v, c), where v is the count and c is the character.
When rearranging the string, we repeatedly pop the top element (v, c) from the heap, add character c to the result string, and push (v-1, c) into a queue q. When the length of the queue q reaches k or more, we pop the front element; if its v is greater than 0, we push it back into the heap. Repeat this process until the heap is empty.
Finally, we check whether the length of the result string equals the original string. If so, we return the result string; otherwise, we return an empty string.
The time complexity is O(n log n), where n is the length of the string. The space complexity is O(|Σ|), where |Σ| is the size of the character set, which is 26 in this problem.
Related problems:
PythonJavaC++GoTypeScript
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)(code-box)
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();
}
}(code-box)
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;
}
};(code-box)
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()
}(code-box)
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('');
}(code-box)
