MediumArrayHash TableStringGreedySortingCountingUpdated Sep 2026

3035. Maximum Palindromes After Operations

Asked at Salesforce

Difficulty

Medium

Time

O(n * L + n log n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You get an array of strings called words. You may swap any two characters, even characters that live in different strings. You can do this swap any number of times, including zero times.

After all the swaps, count how many of the strings are palindromes. A palindrome reads the same forwards and backwards. Return the largest count you can reach.

Because you can move characters freely between strings, only two things matter: the total number of each letter across all strings, and the length of each string. A string of length L needs L // 2 matching pairs of letters, plus at most one single leftover letter if L is odd. So the real question is: how many strings can you fill using the pairs you have?

Characters can travel between strings

wordsabbbbaaa012Start: only "aa" is a palindrome.pool all letterspair them uprefill stringscount palindromesLetters are pooled, then handed back so that as manystrings as possible become palindromes.
Swaps are free and unlimited, so think of all letters as one shared pool that you pour back into the strings.

Constraints

  • ●1 <= words.length <= 1000
  • ●1 <= words[i].length <= 100
  • ●words[i] consists only of lowercase English letters

Examples

Example 1
Inputwords = ["abbb","ba","aa"]
Output3
WhySwap the first 'a' of "abbb" with the first 'b' of "ba". Now the strings are "bbbb", "aa" and "aa". All three read the same in both directions, so the answer is 3.
Example 2
Inputwords = ["abc","ab"]
Output2
WhyMove the 'c' of "abc" into "ab" and bring a 'b' back, giving "aac" and "bb". Then swap the two middle characters of "aac" to get "aca". Both strings are now palindromes, so the answer is 2.
Example 3
Inputwords = ["cd","ef","a"]
Output1
WhyThe letters are c, d, e, f and a — every letter appears exactly once, so there is not a single matching pair. Only the length-1 string "a" is already a palindrome, and no swap can create a pair. The answer is 1.

Asked At

1 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →

How to Think About It

1

Brute force: for each string, try all permutations and check if any is a palindrome. This is exponential.

2

A string can be rearranged into a palindrome if at most one character has an odd frequency.

3

Count the total number of each character across all strings. Use these counts to greedily build palindromes.

4

Sort strings by length. For each string, try to form a palindrome by pairing characters. If you have enough pairs, the string can be a palindrome.

5

Optimal: count character frequencies globally. Each palindrome needs floor(len/2) pairs and can tolerate one odd character. Greedily assign pairs to the longest strings first.

Optimal Approach

Count the total frequency of each character across all strings. Compute how many pairs are available (sum of freq[c] // 2 for each character). Sort the strings by length. For each string from longest to shortest, check if we have enough pairs to fill half the string. If yes, consume those pairs and increment the count. The remaining character (if the string length is odd) can be any leftover character. Return the total count of strings that can be made palindromes.

Count pairs, fill the longest strings first

letter countslettercounta3b4"abbb" + "ba" + "aa" gives a:3 and b:4, so pairs =3//2 + 4//2 = 1 + 2 = 3.sorted by length422012Lengths sorted long to short: 4, 2, 2.len 4 needs 2 pairs → pairs 3→1len 2 needs 1 pair → pairs 1→0len 2 needs 1 pair → not enough
Longer strings need more pairs, so spend pairs on them first — that way you never waste pairs on a short string while a long one stays impossible.
ComplexityTime O(n * L + n log n)Space O(1)Counting letters costs O(n * L); sorting the strings by length costs O(n log n); the alphabet size (26) is constant.

What Trips People Up in Real Interviews

1

Clarify: can we rearrange characters across strings, or only within each string? (Only within each string.)

2

Start by explaining the palindrome condition: at most one odd-frequency character.

3

Discuss the greedy idea: sort strings by length, assign pairs to longest strings first.

4

Use a frequency count to track available character pairs.

5

Walk through an example to show why greedy by length works.

Solution Code

O(n * L + n log n) time
def maxPalindromesAfterOperations(words):
    from collections import Counter
    total = Counter()
    for w in words:
        total += Counter(w)
    pairs = sum(v // 2 for v in total.values())
    words.sort(key=len, reverse=True)
    result = 0
    for w in words:
        needed = len(w) // 2
        if pairs >= needed:
            pairs -= needed
            result += 1
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Palindromes After Operations problem?

You are given an array of strings. You may rearrange the characters in each string arbitrarily. After rearranging, count how many of the strings can be made palindromes. A string is a palindrome if it reads the same forwards and backwards.

How do you solve Maximum Palindromes After Operations?

The optimal approach runs in O(n * L + n log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Palindromes After Operations?

Maximum Palindromes After Operations is asked at Salesforce. It is a medium difficulty problem.

What are common mistakes on Maximum Palindromes After Operations?
  • Clarify: can we rearrange characters across strings, or only within each string? (Only within each string.)
  • Start by explaining the palindrome condition: at most one odd-frequency character.
  • Discuss the greedy idea: sort strings by length, assign pairs to longest strings first.
  • Use a frequency count to track available character pairs.
  • Walk through an example to show why greedy by length works.