Rearrange string k distance apart

Hash Table String Greedy Sorting Heap (Priority Queue) Counting

39.9% acceptance

Mar 31, 2026

1001

No description available.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;

impl Solution {
  pub fn rearrange_string(s: String, k: i32) -> String {
    if k <= 1 {
      return s;
    }
    let k = k as usize;
    let mut freq = [0i32; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    // Max-heap of (count, char)
    let mut heap = BinaryHeap::new();
    for i in 0..26 {
      if freq[i] > 0 {
        heap.push((freq[i], i as u8));
      }
    }
    let mut result = Vec::with_capacity(s.len());
    let mut wait_queue: std::collections::VecDeque<(i32, u8, usize)> = std::collections::VecDeque::new();

    while let Some((cnt, ch)) = heap.pop() {
      result.push(b'a' + ch);
      wait_queue.push_back((cnt - 1, ch, result.len() - 1 + k));
      while let Some(&(wc, wch, release_at)) = wait_queue.front() {
        if result.len() >= release_at {
          wait_queue.pop_front();
          if wc > 0 {
            heap.push((wc, wch));
          }
        } else {
          break;
        }
      }
    }
    if result.len() == s.len() {
      String::from_utf8(result).unwrap()
    } else {
      String::new()
    }
  }
}