Next special palindrome number

impl Solution {
  pub fn special_palindrome(n: i64) -> i64 {
    // Generate all special palindromes in increasing order until we find one > n.
    // A special number has each digit k appearing exactly k times.
    // Digits 0 doesn't appear (0 times = 0), digits 1-9 are possible.
    // Total digits = sum of k * (count of digit k) where each used digit k appears k times.
    //
    // Valid digit multisets: choose a subset S of {1..9} and use digit k exactly k times.
    // Total length = sum(k for k in S).
    // Maximum: if S = {9}, length = 9. If S = {1,9}, length = 10. etc.
    // For n up to 10^15 (16 digits), we need palindromes up to ~16 digits.
    // 
    // Generate all palindromes from valid multisets:
    // For each subset S of {1..9}, generate all palindromes with digit k appearing exactly k times.
    // The total number of such palindromes can be large but let's enumerate them.
    //
    // For palindrome generation: the total length L = sum(S).
    // Half the string (first ceil(L/2) chars) determines the palindrome.
    // Each palindrome of length L: positions 0..L/2 determine the rest.
    // We need each digit k in S to appear exactly k times total (in the whole palindrome).
    //
    // For a palindrome of length L:
    //   If L is even: each position i (0..L/2) mirrors with L-1-i. Each appears twice.
    //     So each half contributes k/2 of each digit k (k must be even for all k in S).
    //   If L is odd: the middle character appears once, others twice in pairs.
    //     The middle char contributes odd count (1), others contribute even (2 each pair).
    //     So at most one digit can have odd count (the middle one).
    //
    // This means: for S to form a palindrome:
    //   sum_odd_digits in S <= 1 (at most one digit with odd k).
    //   If L is even: all k must be even.
    //   If L is odd: exactly one k is odd.
    //
    // Since k = digit itself: odd digits are 1, 3, 5, 7, 9.
    // For even-length palindromes: only even digits {2,4,6,8} subsets.
    // For odd-length palindromes: exactly one odd digit (1,3,5,7,9) plus any even digits.
    //
    // The palindromic first half: place k/2 of each even digit, (k-1)/2 of each odd digit,
    // and 1 of the single odd digit as middle (only if L is odd).
    //
    // Let's enumerate all candidate palindromes efficiently.
    // For each valid subset S and each permutation of the first half, generate the palindrome number.
    // Then sort and find the first one > n.
    //
    // The number of valid subsets is at most 2^9 = 512.
    // For each subset, the first half length can be up to ~8 digits (L up to 16).
    // Number of permutations of half: at most 8! = 40320 but with repetitions much less.
    // Total: manageable.

    use std::collections::BTreeSet;

    fn gen_permutations(digits: &[u8]) -> Vec<Vec<u8>> {
      if digits.is_empty() { return vec![vec![]]; }
      let mut sorted = digits.to_vec();
      sorted.sort();
      let mut result = Vec::new();
      let mut used = vec![false; sorted.len()];
      let mut current = Vec::new();
      gen_perm_helper(&sorted, &mut used, &mut current, &mut result);
      result
    }

    fn gen_perm_helper(sorted: &[u8], used: &mut Vec<bool>, current: &mut Vec<u8>, result: &mut Vec<Vec<u8>>) {
      if current.len() == sorted.len() {
        result.push(current.clone());
        return;
      }
      let mut prev = 255u8;
      for i in 0..sorted.len() {
        if used[i] || sorted[i] == prev { continue; }
        used[i] = true;
        current.push(sorted[i]);
        gen_perm_helper(sorted, used, current, result);
        current.pop();
        used[i] = false;
        prev = sorted[i];
      }
    }

    fn make_palindrome(half: &[u8], middle: Option<u8>, l: usize) -> i64 {
      let mut digits = Vec::with_capacity(l);
      for &d in half { digits.push(d); }
      if let Some(m) = middle { digits.push(m); }
      for i in (0..half.len()).rev() { digits.push(half[i]); }
      if digits[0] == 0 { return -1; } // leading zero
      digits.iter().fold(0i64, |acc, &d| acc * 10 + d as i64)
    }

    let mut candidates: BTreeSet<i64> = BTreeSet::new();

    // Enumerate all valid subsets
    for mask in 1u32..(1 << 9) {
      let subset: Vec<u8> = (1u8..=9).filter(|&k| mask & (1 << (k-1)) != 0).collect();
      let total_len: usize = subset.iter().map(|&k| k as usize).sum();
      // Skip subsets that would produce palindromes too large for i64
      if total_len > 18 { continue; }
      // Count odd-count digits
      let odd_count = subset.iter().filter(|&&k| k % 2 == 1).count();
      if total_len % 2 == 0 {
        if odd_count != 0 { continue; } // even len needs all even counts
      } else {
        if odd_count != 1 { continue; } // odd len needs exactly one odd-count digit
      }
      
      // Build the first half
      let mut half_digits: Vec<u8> = Vec::new();
      let mut middle_digit: Option<u8> = None;
      for &k in &subset {
        if k % 2 == 1 && total_len % 2 == 1 {
          // k appears k times total: (k-1)/2 in half, 1 in middle, (k-1)/2 in mirror
          middle_digit = Some(k);
          for _ in 0..(k-1)/2 { half_digits.push(k); }
        } else {
          // k/2 in each half
          for _ in 0..k/2 { half_digits.push(k); }
        }
      }
      
      // Generate all permutations of half_digits (first half)
      let perms = gen_permutations(&half_digits);
      for perm in perms {
        let val = make_palindrome(&perm, middle_digit, total_len);
        if val > n {
          candidates.insert(val);
        }
      }
    }

    *candidates.iter().next().unwrap()
  }
}