Maximum Palindromes After Operations
Asked at Salesforce
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | MEDIUM | View all Salesforce questions → |
How to Think About It
Brute force: for each string, try all permutations and check if any is a palindrome. This is exponential.
A string can be rearranged into a palindrome if at most one character has an odd frequency.
Count the total number of each character across all strings. Use these counts to greedily build palindromes.
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.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.