We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Palindromes After Operations

Number: 3317

Difficulty: Medium

Paid? No

Companies: MathWorks

Problem Description

Given an array of strings, you are allowed to swap any two characters (even within the same string) arbitrarily many times. The goal is to rearrange the characters among and within the words so that as many words as possible become palindromes. A word can be rearranged into a palindrome if and only if, when counting its characters, at most one character has an odd frequency (that odd frequency is necessary for words with odd lengths, while words with even lengths require all characters to appear an even number of times).

Key Insights

  • Since swaps can be performed arbitrarily between words, the global multiset of characters (i.e. the total frequency of characters across all words) is what matters.
  • A string of even length can form a palindrome if all characters appear an even number of times.
  • A string of odd length can form a palindrome if at most one character appears an odd number of times.
  • The overall strategy is to redistribute characters among words. In this process, extra odd occurrences (i.e. odds that are not “needed” as a center in an odd-length word) can be paired off (each pair can be made even) after proper swaps.
  • A useful formula is: result = n - max(0, (globalOddCount - oddLengthWords) // 2)
    • Here, n is the total number of words.
    • globalOddCount is the count of characters in the combined frequency that appear an odd number of times.
    • oddLengthWords is the number of words with an odd length (since each such word can use one odd occurrence for its center).

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of words and m is the average length of a word
Space Complexity: O(1) (or O(26) to be precise, since we only track counts for lowercase English letters)

Solution

Since we can swap any characters arbitrarily among and within words, the individual order in each word does not matter; what matters is the overall availability of characters. We first compute the total frequency count for every character in all words. From this combined count, we determine how many characters occur an odd number of times (globalOddCount).

Meanwhile, each odd-length word can “absorb” one odd occurrence (for its center in a palindrome). However, extra odd occurrences (beyond the number of odd length words) must be paired to form even counts; each such pair effectively “loses” the chance of making one palindrome (because those extra odds cannot be assigned to a palindrome without creating a violation).

Thus, the maximum number of palindromic words we can obtain is calculated as: result = n - max(0, (globalOddCount - oddLengthWords) // 2)

This greedy redistribution of the letter frequencies ensures that as many words as possible can be arranged into palindromic forms.

Code Solutions

# Python solution with line-by-line comments

def maximumPalindromes(words):
    # n: total number of words
    n = len(words)
    
    # odd_words: count of words with odd length since each can accommodate one odd center
    odd_words = sum(1 for word in words if len(word) % 2 == 1)

    # global frequency counter for characters over all words
    freq = [0] * 26  # for letters 'a' to 'z'
    
    # build the global frequency count
    for word in words:
        for char in word:
            freq[ord(char) - ord('a')] += 1
            
    # count how many characters have an odd frequency
    global_odd = sum(1 for count in freq if count % 2 == 1)
    
    # For every extra pair of odd counts beyond odd_words,
    # we lose the possibility of converting one word to a palindrome.
    # Calculate the pairs that exceed the available odd center spots.
    loss = max(0, (global_odd - odd_words) // 2)
    
    # maximum palindromes is total words minus the losses
    return n - loss

# Example usage:
#print(maximumPalindromes(["abbb","ba","aa"]))   # Expected output: 3
#print(maximumPalindromes(["abc","ab"]))           # Expected output: 2
#print(maximumPalindromes(["cd","ef","a"]))          # Expected output: 1
← Back to All Questions