Skip to main content
Talentd

Maximum Palindromes After Operations - Solution & Explanation

MediumArrayHash TableStringGreedy9 min readAsked at: Microsoft, Visa, Salesforce +5
Practice this problem

Problem Statement

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.

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 <= 1000
  • 1 <= words[i].length <= 100
  • words[i] consists only of lowercase English letters.

Approach Overview

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.

Approach 1: Approach 1: Utilize Frequency Counts

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Construct Palindrome Greedily

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.

Code

JavaC++

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), since we're using a fixed size array to count frequencies of 26 letters.

Approach 2: Construct Palindrome Greedily

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Utilize Frequency CountsO(n log n)O(1)General case. Efficient when you only need pair counts and want a simple greedy allocation.
Construct Palindrome GreedilyO(n log n)O(1)When reasoning about actually building palindromes step‑by‑step helps clarify the greedy allocation.

Video Solution

3035. Maximum Palindromes After Operations | Greedy | Palindrome | String | Sorting • Aryan Mittal • 4,883 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Maximum Palindromes After Operations easy or hard?
Maximum Palindromes After Operations is generally classified as a medium difficulty problem. The challenge comes from recognizing that swaps allow characters to be pooled globally, reducing the task to counting pairs and applying a greedy distribution strategy.
Maximum Palindromes After Operations Python/Java solution
Most implementations first compute a frequency array of size 26, count how many character pairs exist, then sort the word lengths. Python solutions typically use collections.Counter, while Java implementations use an int[26] array. Both follow the same greedy pair allocation logic.
How to solve Maximum Palindromes After Operations in O(n)?
Pure O(n) is difficult because most solutions sort string lengths to apply the greedy strategy. However, the core operations—frequency counting and pair calculation—run in linear time over the characters. With bounded length constraints or counting sort on lengths, the sorting step can be reduced close to linear time.
What is the best approach for Maximum Palindromes After Operations?
The most efficient approach counts the total frequency of characters across all words and converts them into usable pairs. After sorting word lengths, greedily assign pairs to the smallest words first. This ensures the maximum number of palindromes can be formed while keeping time complexity around O(n log n).
Is Maximum Palindromes After Operations asked at Google/Amazon/Meta?
Greedy counting problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern of converting character frequencies into usable pairs and allocating them optimally is a common string and greedy interview concept.
What data structure is used in Maximum Palindromes After Operations?
The solution primarily uses a fixed-size frequency array (or hash table) to store character counts. Sorting is applied to string lengths, and a simple greedy allocation determines how many palindromes can be formed.
What is the time complexity of Maximum Palindromes After Operations?
The optimal solution runs in O(n log n) time where n is the number of strings. Counting character frequencies takes O(total characters), and sorting the string lengths dominates the runtime. Space complexity is O(1) because only a fixed 26‑character frequency array is required.

Ready to solve this problem?

Practice Maximum Palindromes After Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Valid Palindrome