Maximum palindromes after operations

Array Hash Table String Greedy Sorting Counting

45.6% acceptance

Feb 25, 2026

255

You are given a 0-indexed string array words having length n and containing 0-indexed strings. You are allowed to perform the following operation any number of times (including zero): Choose integers i, j, x, and y such that 0 <= i, j < n, 0 <= x < words[i].length, 0 <= y < words[j].length, and swap the characters words[i][x] and words[j][y]. Return an integer denoting the maximum number of palindromes words can contain, after performing some operations.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_palindromes_after_operations(words: Vec<String>) -> i32 {
    let mut freq = [0i32; 26];
    for w in &words { for b in w.bytes() { freq[(b-b'a') as usize] += 1; } }
    let mut pairs: i32 = freq.iter().map(|&f| f / 2).sum();
    let mut lens: Vec<usize> = words.iter().map(|w| w.len()).collect();
    lens.sort();
    let mut ans = 0;
    for &l in &lens {
      let needed = l / 2;
      if pairs >= needed as i32 { pairs -= needed as i32; ans += 1; }
    }
    ans
  }
}