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);
    let s = "aaadbbcc".to_string();
    let k = 2;
    let res = "abacabcd".to_string();
    assert_eq!(Solution::rearrange_string(s, k), res);
}

Having problems with this solution? Click here to submit an issue on github.