Smallest palindromic rearrangement ii

Hash Table Math String Combinatorics Counting

14.4% acceptance

Feb 25, 2026

You are given a palindromic string s and an integer k. Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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

    // Mid character (odd count character)
    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);
      }
    }

    // Half counts
    let mut half = [0i64; 26];
    for i in 0..26 {
      half[i] = cnt[i] / 2;
    }
    let half_len: i64 = half.iter().sum();

    // Check if total permutations >= k
    let total = count_perms_capped(&half, half_len, k);
    if total < k {
      return String::new();
    }

    // Greedily find k-th permutation of first half
    let mut result_half: Vec<u8> = Vec::with_capacity(half_len as usize);
    let mut remaining_k = k;
    let mut cur_len = half_len;

    for _ in 0..half_len {
      // Fast-path: if M > remaining_k * cur_len then every single character
      // choice (even one with count=1) still gives > remaining_k permutations.
      // In that case just pick the lexicographically smallest available char.
      let threshold = remaining_k.saturating_mul(cur_len);
      if count_perms_capped(&half, cur_len, threshold) > threshold {
        let c = (0..26).position(|i| half[i] > 0).unwrap();
        result_half.push(b'a' + c as u8);
        half[c] -= 1;
        cur_len -= 1;
        continue;
      }

      for c in 0..26 {
        if half[c] == 0 { continue; }
        half[c] -= 1;
        cur_len -= 1;
        let cnt_here = count_perms_capped(&half, cur_len, remaining_k);
        if cnt_here >= remaining_k {
          result_half.push(b'a' + c as u8);
          break;
        } else {
          remaining_k -= cnt_here;
          half[c] += 1;
          cur_len += 1;
        }
      }
    }

    // Build palindrome
    let mut res = result_half.clone();
    if let Some(mc) = mid_char {
      res.push(mc);
    }
    res.extend(result_half.iter().rev());
    String::from_utf8(res).unwrap()
  }
}

/// Count distinct permutations of chars with given half[] counts, total length = total.
/// Caps at cap+1 if result > cap (returns cap+1 to signal "exceeds cap").
fn count_perms_capped(half: &[i64; 26], total: i64, cap: i64) -> i64 {
  // Multinomial: total! / prod(half[c]!)
  // Compute using: C(rem, half[c]) iteratively via i128 to avoid mid-step overflow.
  let big = (cap + 1) as i128;
  let mut result: i128 = 1;
  let mut rem = total as i128;
  for &c in half {
    if c == 0 { continue; }
    let c128 = c as i128;
    // Compute result *= C(rem, c) step by step.
    // Use min(c, rem-c) iterations since C(rem,c) = C(rem, rem-c).
    // This keeps intermediate values small when c is large (e.g. c ≈ rem),
    // preventing spurious i128 overflow that would give a wrong early return.
    let eff = c128.min(rem - c128);
    for i in 0i128..eff {
      let num = rem - i;
      let den = i + 1;
      // Guard against i128 overflow.
      if num > 0 && result > i128::MAX / num {
        return cap + 1;
      }
      result = result * num / den;
    }
    rem -= c128;
    // Cap check after the complete C(rem, c) is folded in.
    if result >= big {
      return cap + 1;
    }
  }
  result as i64
}