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):
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.
Note: i and j may be equal during an operation.
Example 1:
Input: words = ["abbb","ba","aa"] Output: 3 Explanation: In this example, one way to get the maximum number of palindromes is: Choose i = 0, j = 1, x = 0, y = 0, so we swap words[0][0] and words[1][0]. words becomes ["bbbb","aa","aa"]. All strings in words are now palindromes. Hence, the maximum number of palindromes achievable is 3.
Example 2:
Input: words = ["abc","ab"] Output: 2 Explanation: In this example, one way to get the maximum number of palindromes is: Choose i = 0, j = 1, x = 1, y = 0, so we swap words[0][1] and words[1][0]. words becomes ["aac","bb"]. Choose i = 0, j = 0, x = 1, y = 2, so we swap words[0][1] and words[0][2]. words becomes ["aca","bb"]. Both strings are now palindromes. Hence, the maximum number of palindromes achievable is 2.
Example 3:
Input: words = ["cd","ef","a"] Output: 1 Explanation: In this example, there is no need to perform any operation. There is one palindrome in words "a". It can be shown that it is not possible to get more than one palindrome after any number of operations. Hence, the answer is 1.
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 100words[i] consists only of lowercase English letters.Problem Overview: You receive an array of strings. Characters can be swapped between any strings. After performing any number of swaps, determine the maximum number of strings that can be rearranged into palindromes.
The key observation: swaps make character positions irrelevant across words. Only the total character counts matter. A string of length k needs k/2 character pairs to form mirrored positions. If the length is odd, one extra character can sit in the center.
Approach 1: Utilize Frequency Counts (O(n log n) time, O(1) space)
Count the total frequency of each character across all words using a simple array or hash map from the hash table family of techniques. From these counts, compute the number of available pairs (freq // 2). Each palindrome requires len(word) // 2 pairs. Sort the word lengths in ascending order using a sorting strategy, then greedily allocate pairs to shorter words first. This works because shorter words require fewer resources, allowing you to build more palindromes overall. If enough pairs exist for a word, construct the palindrome conceptually and subtract the used pairs. The remaining characters automatically cover the middle position for odd lengths. This approach is efficient because character counts are bounded (26 lowercase letters), so the extra memory stays constant.
Approach 2: Construct Palindrome Greedily (O(n log n) time, O(1) space)
This approach models the process more directly. First aggregate all character counts using a array of size 26. Convert those counts into a pool of available pairs. Next sort the strings by length. For each string, attempt to construct its palindrome by consuming pairs from the pool. A string of length L needs L/2 mirrored pairs; the center character (if L is odd) can always be filled because leftover characters exist once pairs are broken down. The greedy rule remains the same: allocate pairs to the smallest strings first so that pair resources are distributed to the maximum number of strings.
Recommended for interviews: The frequency-count + greedy allocation approach is what interviewers usually expect. It shows you recognize that cross-string swaps eliminate positional constraints and reduce the problem to pair counting. Starting with raw counting demonstrates understanding, while the sorted greedy allocation shows algorithmic optimization using greedy reasoning.
To determine the maximum number of palindromes, you can start by checking the frequency of each character across all words. A string can be rearranged into a palindrome if at most one character has an odd frequency while others have even frequencies.
Therefore, by calculating the frequency of characters, you can determine the maximum potential palindromes by freely swapping characters to achieve evenly distributed counts across the words.
This solution uses a counter to aggregate the frequency of each character across all words. The sum of characters with odd frequencies indicates how many swaps are minimally required to potentially form a palindrome. Since two words can share a character swap to even out odd frequencies, the number of palindromes is maximized by leveraging these swaps.
Python
JavaScript
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), since we're using a fixed size array to count frequencies of 26 letters.
In this method, you attempt to form a palindrome for each word independently and count how many times that is possible. If a word already forms a palindrome, it contributes directly to the count. If not, determine if character swaps between all available words can resolve the imbalance.
The Java version here first checks if any word is a palindrome naturally. For non-palindrome words, it count frequencies and odd counts just like before.
Time Complexity: O(n * m), with n, m as number of words and average length, respectively.
Space Complexity: O(1) for the character frequency map size determined by a fixed character set.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Utilize Frequency Counts | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| Approach 2: Construct Palindrome Greedily | Time Complexity: O(n * m), with n, m as number of words and average length, respectively. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Utilize Frequency Counts | O(n log n) | O(1) | General case. Efficient when you only need pair counts and want a simple greedy allocation. |
| Construct Palindrome Greedily | O(n log n) | O(1) | When reasoning about actually building palindromes step‑by‑step helps clarify the greedy allocation. |
3035. Maximum Palindromes After Operations | Greedy | Palindrome | String | Sorting • Aryan Mittal • 4,649 views views
Watch 9 more video solutions →Practice Maximum Palindromes After Operations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor