LeetCode Problem 3035

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Greedy, Sorting, Counting

Solution

LeetCode 3035 - Maximum Palindromes After Operations

Problem Understanding

This problem gives us an array of strings, words, and allows us to swap any character with any other character across the entire collection of strings. The swaps are completely unrestricted. We may swap characters between different strings, within the same string, or perform no operations at all.

Because we can perform an unlimited number of swaps, the actual positions of characters inside the original strings become irrelevant. The only thing that matters is the total multiset of characters available across all words.

The goal is to maximize the number of strings that can become palindromes after redistributing the characters through these swaps.

A palindrome has a simple frequency requirement:

• For a string of even length, every character count must be even.
• For a string of odd length, exactly one character may have an odd count, and all remaining counts must be even.

The input consists of up to 1000 strings, each with length up to 100. Therefore, the total number of characters is at most 100,000.

The output is a single integer representing the maximum number of words that can simultaneously be made palindromic after performing any number of swaps.

The most important observation is that character identities matter only through their frequencies. Since swaps allow complete redistribution, we can think of all characters being placed into a common pool and then assigned back to strings in whatever way is most beneficial.

Several edge cases are worth noting:

• Single-character strings are always palindromes.
• If there are very few character pairs available, long strings may be impossible to make palindromic.
• Odd-length strings require a center character, but every character in the global pool can serve as a center.
• The optimal strategy may involve making shorter strings palindromic first because they require fewer character pairs.

Approaches

Brute Force

A brute-force solution would attempt to redistribute characters among strings in every possible way and count how many palindromes can be formed.

Since the total number of characters can be as large as 100,000, the number of possible redistributions is astronomically large. Even for very small inputs, enumerating all assignments of characters to strings is infeasible.

While such an approach would eventually find the optimal answer, it is completely impractical for the given constraints.

Key Insight

Since arbitrary swaps allow us to rearrange all characters globally, the only resource that truly matters is the number of character pairs available.

Suppose a character appears f times. It contributes f // 2 usable pairs.

For a word of length L:

• It needs L // 2 pairs to fill its mirrored positions.
• If L is odd, it also needs one center character.

The center character requirement is never the limiting factor. After allocating pairs, every unused character and every pair can provide characters for centers.

Therefore, the entire problem reduces to:

1. Count the total number of character pairs available.
2. Sort word lengths in ascending order.
3. Greedily satisfy the smallest pair requirements first.
4. Count how many words can be completed before running out of pairs.

The greedy strategy is optimal because a shorter word consumes fewer pairs. If we cannot afford a smaller word, we certainly cannot afford a larger one.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all character redistributions
Optimal	O(n log n + T)	O(1)	Counts available pairs and greedily allocates them

Here, n is the number of words and T is the total number of characters.

Algorithm Walkthrough

1. Count the frequency of every character across all words.

Since characters can move freely between words, we only care about global frequencies. 2. Compute the total number of available pairs.

For every character frequency f, add f // 2 to a running total. 3. Extract the length of every word.

The pair requirement of a word depends only on its length. 4. Sort the lengths in ascending order.

Smaller words require fewer pairs and should be satisfied first. 5. Iterate through the sorted lengths.

For a word of length L, compute:

required_pairs = L // 2

6. Check whether enough pairs remain.

If the available pair count is at least required_pairs, consume those pairs and count the word as palindromic. 7. If insufficient pairs remain, stop.

Since lengths are sorted, every remaining word requires at least as many pairs. None of them can be formed. 8. Return the number of successfully formed palindromes.

Why it works

A palindrome of length L requires exactly L // 2 mirrored character pairs. The total supply of such pairs is fixed by the global character frequencies. Since every word's requirement depends only on its length, maximizing the number of palindromes becomes identical to maximizing the number of pair-requirements that can be satisfied. Sorting lengths and satisfying the cheapest requirements first is the classic optimal greedy strategy. Any solution that skips a smaller requirement in favor of a larger one can never produce more completed palindromes.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def maxPalindromesAfterOperations(self, words: List[str]) -> int:
        freq = Counter()

        for word in words:
            freq.update(word)

        available_pairs = sum(count // 2 for count in freq.values())

        lengths = sorted(len(word) for word in words)

        answer = 0

        for length in lengths:
            needed_pairs = length // 2

            if available_pairs < needed_pairs:
                break

            available_pairs -= needed_pairs
            answer += 1

        return answer

The implementation begins by building a global frequency table for all characters. Because swaps are unrestricted, individual word frequencies do not matter.

Next, it computes the total number of usable character pairs. Every palindrome requires mirrored positions, and each mirrored position pair consumes one character pair from the global pool.

The word lengths are then collected and sorted. Sorting is crucial because it enables the greedy strategy of satisfying the cheapest requirements first.

For each length, the algorithm calculates how many pairs are needed. If enough pairs remain, they are consumed and the palindrome count increases. Once the remaining pairs are insufficient for the current word, the loop terminates because every later word requires at least as many pairs.

The final count is returned as the answer.

Go Solution

package main

import "sort"

func maxPalindromesAfterOperations(words []string) int {
	var freq [26]int

	for _, word := range words {
		for _, ch := range word {
			freq[ch-'a']++
		}
	}

	availablePairs := 0
	for _, count := range freq {
		availablePairs += count / 2
	}

	lengths := make([]int, len(words))
	for i, word := range words {
		lengths[i] = len(word)
	}

	sort.Ints(lengths)

	answer := 0

	for _, length := range lengths {
		neededPairs := length / 2

		if availablePairs < neededPairs {
			break
		}

		availablePairs -= neededPairs
		answer++
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. Since the alphabet consists only of lowercase English letters, a fixed-size array of length 26 is used instead of a hash map. This slightly reduces overhead and keeps the solution efficient. No overflow concerns exist because the total number of characters is at most 100,000, well within Go's integer range.

Worked Examples

Example 1

Input:

["abbb", "ba", "aa"]

Character frequencies:

Character	Count
a	3
b	4

Available pairs:

Character	Pairs
a	1
b	2

Total pairs = 3

Word lengths:

[4, 2, 2]

Sorted lengths:

[2, 2, 4]

Length	Pairs Needed	Remaining Pairs	Palindromes
2	1	2	1
2	1	1	2
4	2	Not enough? No, exactly enough	3

Answer:

3

Example 2

Input:

["abc", "ab"]

Character frequencies:

Character	Count
a	2
b	2
c	1

Available pairs:

1 + 1 + 0 = 2

Sorted lengths:

[2, 3]

Length	Pairs Needed	Remaining Pairs	Palindromes
2	1	1	1
3	1	0	2

Answer:

2

Example 3

Input:

["cd", "ef", "a"]

Character frequencies:

Character	Count
a	1
c	1
d	1
e	1
f	1

Available pairs:

0

Sorted lengths:

[1, 2, 2]

Length	Pairs Needed	Remaining Pairs	Palindromes
1	0	0	1
2	1	insufficient	stop

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(T + n log n)	Counting characters takes O(T), sorting lengths takes O(n log n)
Space	O(1)	Only a fixed-size frequency table is needed

Here, T denotes the total number of characters across all words.

The dominant work consists of counting character frequencies and sorting the word lengths. Since the alphabet contains only 26 lowercase letters, the frequency storage remains constant size regardless of input size.

Test Cases

from typing import List

s = Solution()

assert s.maxPalindromesAfterOperations(["abbb", "ba", "aa"]) == 3  # example 1
assert s.maxPalindromesAfterOperations(["abc", "ab"]) == 2  # example 2
assert s.maxPalindromesAfterOperations(["cd", "ef", "a"]) == 1  # example 3

assert s.maxPalindromesAfterOperations(["a"]) == 1  # single character
assert s.maxPalindromesAfterOperations(["aa"]) == 1  # already palindrome
assert s.maxPalindromesAfterOperations(["ab"]) == 0  # no available pair

assert s.maxPalindromesAfterOperations(["a", "b", "c"]) == 3  # all length 1
assert s.maxPalindromesAfterOperations(["aaaa"]) == 1  # one long palindrome
assert s.maxPalindromesAfterOperations(["ab", "cd", "ef"]) == 0  # no pairs anywhere

assert s.maxPalindromesAfterOperations(["aa", "bb", "cc"]) == 3  # every word possible
assert s.maxPalindromesAfterOperations(["aaa", "bbb", "ccc"]) == 3  # odd lengths

assert s.maxPalindromesAfterOperations(["abcdef", "gh"]) == 0  # insufficient pairs
assert s.maxPalindromesAfterOperations(["aabbcc", "dd", "ee"]) == 3  # enough pairs for all

assert s.maxPalindromesAfterOperations(["aaaaaa", "bb", "cc", "dd"]) == 4  # greedy succeeds

Test Case Summary

Test	Why
["abbb","ba","aa"]	Official example 1
["abc","ab"]	Official example 2
["cd","ef","a"]	Official example 3
["a"]	Smallest possible input
["aa"]	Simple even palindrome
["ab"]	Even length with no pair
["a","b","c"]	All words length 1
["aaaa"]	Single long word
["ab","cd","ef"]	No pairs available
["aa","bb","cc"]	Multiple guaranteed palindromes
["aaa","bbb","ccc"]	Odd-length palindromes
["abcdef","gh"]	Not enough pairs
["aabbcc","dd","ee"]	Exact pair allocation
["aaaaaa","bb","cc","dd"]	Greedy allocation stress test

Edge Cases

All Words Have Length One

When every word has length one, each word is automatically a palindrome. A buggy implementation might incorrectly require character pairs for every palindrome. Since a length-one palindrome needs zero pairs, the algorithm correctly counts every word.

No Character Pairs Exist

Consider an input such as ["ab", "cd", "ef"]. Every character appears exactly once, so the number of available pairs is zero. Any even-length palindrome requires at least one pair. The algorithm immediately fails the first length-two requirement and correctly returns zero.

Large Imbalance in Word Lengths

Suppose there is one very long word and many short words. The long word may consume most available pairs. A non-greedy strategy could allocate pairs to the long word first and reduce the total number of palindromes. Sorting lengths ensures the smallest requirements are satisfied first, which maximizes the count of completed palindromes.

Odd-Length Strings and Center Characters

A common misconception is that odd-length palindromes require special handling for center characters. In reality, after allocating the necessary mirrored pairs, the remaining characters always provide enough centers. Therefore the algorithm only needs to track pair availability. This significantly simplifies the solution and avoids unnecessary bookkeeping.