## 358. Rearrange String k Distance Apart

Given a non-empty string s and 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:

```Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least distance 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 distance 2 from each other.
```

## Rust Solution

``````struct Solution;

use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::VecDeque;

impl Solution {
fn rearrange_string(s: String, k: i32) -> String {
let mut count = vec![0; 26];
let k = k as usize;
let mut queue: BinaryHeap<(usize, Reverse<char>)> = BinaryHeap::new();
let mut waiting: VecDeque<(usize, char)> = VecDeque::new();
let mut index = vec![0; 26];
for b in s.bytes() {
count[(b - b'a') as usize] += 1;
}

for i in 0..26 {
if count[i] > 0 {
queue.push((count[i], Reverse((b'a' + i as u8) as char)));
}
}

let mut res = "".to_string();
while !queue.is_empty() {
let mut found = false;
while let Some((count, Reverse(c))) = queue.pop() {
if index[(c as u8 - b'a') as usize] > res.len() {
waiting.push_back((count, c));
} else {
found = true;
index[(c as u8 - b'a') as usize] = res.len() + k;
res.push((c) as char);
if count - 1 > 0 {
waiting.push_back((count - 1, c));
}
break;
}
}
if !found {
return "".to_string();
}
while let Some((count, c)) = waiting.pop_front() {
queue.push((count, Reverse(c)));
}
}
res
}
}

#[test]
fn test() {
let s = "aabbcc".to_string();
let k = 3;
let res = "abcabc".to_string();
assert_eq!(Solution::rearrange_string(s, k), res);
let s = "aaabc".to_string();
let k = 3;
let res = "".to_string();
assert_eq!(Solution::rearrange_string(s, k), res);