Lexicographically smallest palindromic permutation greater than target

impl Solution {
  pub fn lex_palindromic_permutation(s: String, target: String) -> String {
    let n = s.len();
    let mut freq = [0i32; 26];
    for c in s.bytes() {
      freq[(c - b'a') as usize] += 1;
    }

    // A palindromic permutation exists iff at most one character has odd frequency.
    let odd_count = freq.iter().filter(|&&f| f % 2 == 1).count();
    if n % 2 == 0 && odd_count > 0 {
      return String::new();
    }
    if n % 2 == 1 && odd_count != 1 {
      return String::new();
    }

    // Build first-half frequencies (each first-half position consumes one unit).
    let mut half = [0i32; 26];
    for i in 0..26 {
      half[i] = freq[i] / 2;
    }
    let mid_char: Option<u8> = if n % 2 == 1 {
      let c = freq.iter().position(|&f| f % 2 == 1).unwrap();
      Some(b'a' + c as u8)
    } else {
      None
    };

    let t: Vec<u8> = target.bytes().collect();
    let mut p = vec![0u8; n];
    if let Some(mc) = mid_char {
      p[n / 2] = mc;
    }

    // Greedy backtracking over all palindrome positions 0..n:
    //   - First-half positions (pos < mirror): try available chars >= t[pos] (when !greater),
    //     place the chosen char at both pos and its mirror.
    //   - Middle position (pos == mirror, odd n): fixed to mid_char.
    //   - Second-half positions (pos > mirror): already set; compare with t[pos] to update state.
    //
    // `greater` tracks whether the prefix p[0..pos) is already lexicographically > t[0..pos).
    fn backtrack(
      pos: usize,
      n: usize,
      half: &mut [i32; 26],
      mid_char: Option<u8>,
      t: &[u8],
      p: &mut Vec<u8>,
      greater: bool,
    ) -> bool {
      if pos == n {
        return greater;
      }
      let mirror = n - 1 - pos;
      if pos > mirror {
        // Second half: character already set by mirroring.
        // Must compare p[pos] vs t[pos] to correctly propagate `greater`.
        let ch = p[pos];
        if !greater && ch < t[pos] {
          return false;
        }
        let new_g = greater || ch > t[pos];
        return backtrack(pos + 1, n, half, mid_char, t, p, new_g);
      }
      if pos == mirror {
        // Middle character (odd-length string).
        let mc = mid_char.unwrap();
        p[pos] = mc;
        if !greater && mc < t[pos] {
          return false;
        }
        let new_g = greater || mc > t[pos];
        return backtrack(pos + 1, n, half, mid_char, t, p, new_g);
      }
      // First half: choose the smallest available char that keeps p >= t at this position.
      let min_c = if greater { 0 } else { (t[pos] - b'a') as usize };
      for c in min_c..26 {
        if half[c] == 0 {
          continue;
        }
        let ch = b'a' + c as u8;
        let new_g = greater || ch > t[pos];
        half[c] -= 1;
        p[pos] = ch;
        p[mirror] = ch;
        if backtrack(pos + 1, n, half, mid_char, t, p, new_g) {
          return true;
        }
        half[c] += 1;
      }
      false
    }

    if backtrack(0, n, &mut half, mid_char, &t, &mut p, false) {
      String::from_utf8(p).unwrap()
    } else {
      String::new()
    }
  }
}