Make string anti palindrome

impl Solution {
  pub fn make_anti_palindrome(s: String) -> String {
    let n = s.len();
    let half = n / 2;
    let mut freq = [0usize; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    
    // If any character appears more than half the length, impossible
    if freq.iter().any(|&f| f > half) {
      return "-1".to_string();
    }
    
    // Sort to get lexicographically smallest arrangement
    let mut chars: Vec<u8> = s.bytes().collect();
    chars.sort();
    
    // After sorting, check if s[i] == s[n-1-i] for the first half.
    // We need to fix collisions where chars[i] == chars[n-1-i].
    // The collision happens when the most frequent char fills the middle.
    // Strategy: find the rightmost position in first half that has collision,
    // and swap with the leftmost non-colliding position in second half.
    
    let mut result = chars.clone();
    
    // Find collisions in first half (i and n-1-i)
    // We swap from the end of first half with elements from the start of second half
    let mut j = half; // pointer into second half starting at half
    for i in (0..half).rev() {
      if result[i] == result[n - 1 - i] {
        // Need to swap result[n-1-i] with some result[j] in second half where result[j] != result[i]
        while j < n && result[j] == result[i] {
          j += 1;
        }
        if j >= n {
          return "-1".to_string();
        }
        result.swap(n - 1 - i, j);
        j += 1;
      }
    }
    
    String::from_utf8(result).unwrap()
  }
}