Smallest palindromic rearrangement i

String Sorting Counting Sort

63.5% acceptance

Feb 25, 2026

You are given a palindromic string s. Return the lexicographically smallest palindromic permutation of s.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_palindrome(s: String) -> String {
    let _n = s.len();
    let mut cnt = [0u32; 26];
    for b in s.bytes() {
      cnt[(b - b'a') as usize] += 1;
    }

    // Build first half in sorted order
    let mut half: Vec<u8> = Vec::new();
    let mut mid_char: Option<u8> = None;
    for i in 0..26 {
      if cnt[i] % 2 == 1 {
        mid_char = Some(b'a' + i as u8);
      }
      for _ in 0..cnt[i] / 2 {
        half.push(b'a' + i as u8);
      }
    }

    // Build the palindrome: half + optional_middle + reverse(half)
    let mut result = half.clone();
    if let Some(c) = mid_char {
      result.push(c);
    }
    result.extend(half.iter().rev());

    String::from_utf8(result).unwrap()
  }
}