Reorganize string

Hash Table String Greedy Sorting Heap (Priority Queue) Counting

56.8% acceptance

Feb 21, 2026

9192

285

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. Return any possible rearrangement of s or return "" if not possible.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

/*
 * Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
 * Return any possible rearrangement of s or return "" if not possible.
 * Example 1:
 * Input: s = "aab"
 * Output: "aba"
 * Example 2:
 * Input: s = "aaab"
 * Output: ""
 * Constraints:
 * 1 <= s.length <= 500
 * s consists of lowercase English letters.
 */
impl Solution {
  pub fn reorganize_string(s: String) -> String {
    let mut freq = [0i32; 26];
    for b in s.bytes() { freq[(b - b'a') as usize] += 1; }
    let n = s.len();
    let max_f = *freq.iter().max().unwrap();
    if max_f > (n as i32 + 1) / 2 { return "".to_string(); }
    let mut result = vec![b'a'; n];
    let mut pos = 0usize;
    let mut chars: Vec<usize> = (0..26).filter(|&i| freq[i] > 0).collect();
    chars.sort_by(|&a, &b| freq[b].cmp(&freq[a]));
    for c in chars {
      while freq[c] > 0 {
        result[pos] = b'a' + c as u8;
        freq[c] -= 1;
        pos += 2;
        if pos >= n { pos = 1; }
      }
    }
    String::from_utf8(result).unwrap()
  }
}