Palindrome permutation ii

Hash Table String Backtracking

42.3% acceptance

Mar 31, 2026

899

Given a string s, return all the palindromic permutations (without duplicates) of it. You may return the answer in any order. If s has no palindromic permutation, return an empty list.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn generate_palindromes(s: String) -> Vec<String> {
    let mut freq = [0u8; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    let mut odd_char: Option<u8> = None;
    let mut half = Vec::new();
    for i in 0..26 {
      if freq[i] % 2 == 1 {
        if odd_char.is_some() {
          return vec![];
        }
        odd_char = Some(b'a' + i as u8);
      }
      for _ in 0..freq[i] / 2 {
        half.push(b'a' + i as u8);
      }
    }
    let mut result = Vec::new();
    let mut used = vec![false; half.len()];
    let mut current = Vec::new();
    Self::backtrack(&half, &mut used, &mut current, &mut result, odd_char);
    result
  }
  
  fn backtrack(half: &[u8], used: &mut Vec<bool>, current: &mut Vec<u8>, result: &mut Vec<String>, odd_char: Option<u8>) {
    if current.len() == half.len() {
      let mut s: Vec<u8> = current.clone();
      if let Some(c) = odd_char {
        s.push(c);
      }
      let rev: Vec<u8> = current.iter().rev().cloned().collect();
      s.extend(rev);
      result.push(String::from_utf8(s).unwrap());
      return;
    }
    for i in 0..half.len() {
      if used[i] {
        continue;
      }
      if i > 0 && half[i] == half[i - 1] && !used[i - 1] {
        continue;
      }
      used[i] = true;
      current.push(half[i]);
      Self::backtrack(half, used, current, result, odd_char);
      current.pop();
      used[i] = false;
    }
  }
}