Rearrange letters across multiple words to maximize how many words can be turned into palindromes.
You are given an array of words. In one operation, you may take a character from any word and place it into any other word, preserving the total multiset of characters across all words.
Your task is to determine the maximum number of words that can be rearranged into palindromes after any number of such operations.
A word can be rearranged into a palindrome if its characters can be permuted so that the word reads the same forward and backward.
Input Format
- An array of strings
words. - Each string contains lowercase English letters.
Output Format
- Return an integer: the maximum number of words that can be made palindromes after arbitrary transfers of characters between words.
Constraints
- 1 <= words.length
- Each word has length at least 1.
- Only lowercase English letters are used.
- The exact platform constraints are not provided in the source metadata, so treat this as a standard interview version of the problem.
Example 1
Input
words = ["abbb","ba","aa"]
Output
3
Explanation
By rearranging letters, all three words can become palindromes: "bbbb", "aa", and "aa". One possible way is to move letters between words so the total letters are redistributed to satisfy each length's palindrome requirement.
Example 2
Input
words = ["abc","def","gh"]
Output
1
Explanation
Only one word of length 3 can be made into a palindrome using the available letters; the length-2 word would need one matching pair, which is not available after best redistribution.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.