Problem Description

You have an array of strings called words, where each string contains exactly two lowercase English letters.

Your task is to create the longest possible palindrome by:

• Selecting some strings from words
• Concatenating them in any order you choose
• Using each string at most once

Return the length of the longest palindrome you can create. If no palindrome can be formed, return 0.

A palindrome reads the same forward and backward.

For example, if words = ["ab", "ba", "cc", "cc"], you could form:

• "abccccba" (length 8) by using "ab", "cc", "cc", "ba"
• The two "cc" strings form the middle "cccc", while "ab" and "ba" form the outer parts

The key insight is that:

• Strings with identical letters (like "aa", "cc") can be placed in pairs around the palindrome, with potentially one extra in the middle
• Strings with different letters (like "ab") need their reverse counterpart (like "ba") to maintain palindrome symmetry

Intuition

To build a palindrome, we need to think about what makes a valid palindrome structure. Since we're concatenating 2-letter strings, let's consider what types of strings can contribute to a palindrome:

1. Strings with identical letters (like "aa", "bb", "cc"): These are already palindromes themselves. We can place them anywhere in our final palindrome. Specifically, we can use pairs of such strings symmetrically around the center. If we have an odd number of any such string, we can place one in the middle.

2. Strings with different letters (like "ab", "cd"): For these to contribute to a palindrome, we need their reverse counterpart. For example, if we have "ab", we need "ba" to maintain symmetry. We place "ab" on one side and "ba" on the corresponding position on the other side.

The greedy approach emerges from maximizing the use of available strings:

• For identical-letter strings: Use as many pairs as possible (v // 2 * 2 gives us the even count). Each pair contributes 4 to the total length (2 letters per string × 2 strings).
• For different-letter strings: Use min(v, cnt[reversed]) pairs, ensuring we don't exceed what's available for either the string or its reverse. Each pair contributes 4 to the length.
• Finally, if we have any leftover identical-letter strings (tracked by x), we can place exactly one in the center of the palindrome, adding 2 more to the length.

This approach ensures we use the maximum number of strings while maintaining the palindrome property.

Learn more about Greedy patterns.

Solution Approach

We use a greedy approach with a hash table to count occurrences and build the maximum palindrome.

Step 1: Count Word Occurrences

cnt = Counter(words)

Create a hash table to store the frequency of each word. This allows us to quickly access how many times each word appears.

Step 2: Initialize Variables

ans = x = 0

• ans: tracks the total length of the palindrome
• x: counts words with identical letters that appear an odd number of times

Step 3: Process Each Word Type

for k, v in cnt.items():

Iterate through each unique word k and its count v.

Case 1: Words with Identical Letters (k[0] == k[1])

if k[0] == k[1]:
    x += v & 1
    ans += v // 2 * 2 * 2

• v & 1: checks if count is odd (bitwise AND with 1). If odd, increment x
• v // 2 * 2: gives us the even count (number of words we can use in pairs)
• Multiply by 2 again because each word has 2 letters
• Example: If we have 5 "aa" strings, we use 4 of them (2 pairs), contributing 8 to length

Case 2: Words with Different Letters (k[0] != k[1])

else:
    ans += min(v, cnt[k[::-1]]) * 2

• k[::-1]: reverses the word (e.g., "ab" becomes "ba")
• min(v, cnt[k[::-1]]): finds how many matching pairs we can form
• Multiply by 2 because each word has 2 letters
• Example: If we have 3 "ab" and 2 "ba", we can form 2 pairs, contributing 8 to length

Step 4: Add Center Word if Possible

ans += 2 if x else 0

If we have any word with identical letters appearing an odd number of times (x > 0), we can place one such word in the center of the palindrome, adding 2 more to the length.

Time Complexity: O(n) where n is the number of words Space Complexity: O(n) for the hash table

Example Walkthrough

Let's walk through the solution with words = ["ab", "ba", "aa", "aa", "cc"].

Step 1: Count Word Occurrences Create a frequency map:

• "ab": 1
• "ba": 1
• "aa": 2
• "cc": 1

Step 2: Initialize Variables

• ans = 0 (total palindrome length)
• x = 0 (count of identical-letter words with odd frequency)

Step 3: Process Each Word

Processing "ab" (count = 1):

• Since "a" ≠ "b", this is a different-letter word
• Check for reverse: "ba" has count = 1
• Can form min(1, 1) = 1 pair
• Add to answer: ans += 1 * 2 = 2 (each word has 2 letters)
• Running total: ans = 2

Processing "ba" (count = 1):

• Since "b" ≠ "a", this is a different-letter word
• Check for reverse: "ab" has count = 1
• Can form min(1, 1) = 1 pair
• Add to answer: ans += 1 * 2 = 2
• Running total: ans = 4

Processing "aa" (count = 2):

• Since "a" = "a", this is an identical-letter word
• Check if count is odd: 2 & 1 = 0 (even), so x stays 0
• Use in pairs: 2 // 2 * 2 = 2 words can be used
• Add to answer: ans += 2 * 2 = 4 (2 words × 2 letters each)
• Running total: ans = 8

Processing "cc" (count = 1):

• Since "c" = "c", this is an identical-letter word
• Check if count is odd: 1 & 1 = 1 (odd), so x = 1
• Use in pairs: 1 // 2 * 2 = 0 words can be used in pairs
• Add to answer: ans += 0 * 2 = 0
• Running total: ans = 8

Step 4: Add Center Word Since x = 1 (we have an odd-count identical-letter word "cc"), we can place it in the center:

• ans += 2
• Final answer: ans = 10

Resulting Palindrome: One possible arrangement is "abaaccaaba" (length 10)

• "ab" + "aa" + "cc" + "aa" + "ba"
• The pair of "aa" and the pair "ab"/"ba" are placed symmetrically, with "cc" in the center

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of words in the input list. This is because:

• Creating the Counter takes O(n) time as it needs to iterate through all words once
• The subsequent loop iterates through the unique words in the Counter, which is at most n iterations
• Each operation inside the loop (string comparison, reversal, arithmetic operations, and dictionary lookups) takes O(1) time since each word has fixed length of 2
• Therefore, the overall time complexity is O(n) + O(n) = O(n)

The space complexity is O(n), where n is the number of words. This is because:

• The Counter cnt stores at most n unique words as keys with their frequencies as values, requiring O(n) space in the worst case when all words are unique
• Other variables (ans, x, k, v) use constant space O(1)
• The string reversal k[::-1] creates a temporary string of size 2, which is O(1)
• Therefore, the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Double Counting Non-Palindromic Pairs

The Problem: When processing non-palindromic words like "ab" and "ba", the current implementation counts each pair twice:

• When processing "ab", it counts pairs with "ba"
• When processing "ba", it counts the same pairs with "ab" again

This leads to an incorrect result that's double the actual palindrome length.

Example:

words = ["ab", "ba", "cd", "dc"]
# Current code would incorrectly calculate:
# - When processing "ab": min(1, 1) * 2 = 2
# - When processing "ba": min(1, 1) * 2 = 2 (double counting!)
# - When processing "cd": min(1, 1) * 2 = 2
# - When processing "dc": min(1, 1) * 2 = 2 (double counting!)
# Total: 8 (incorrect, should be 4)

Solution: Mark processed pairs or only count each pair once by checking if we've already processed the reverse:

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        from collections import Counter
      
        word_count = Counter(words)
        result = 0
        odd_palindrome_exists = False
        processed = set()
      
        for word, frequency in word_count.items():
            if word in processed:
                continue
              
            if word[0] == word[1]:
                # Palindromic word
                if frequency % 2 == 1:
                    odd_palindrome_exists = True
                result += (frequency // 2) * 4
            else:
                # Non-palindromic word
                reversed_word = word[::-1]
                if reversed_word in word_count:
                    pairs = min(frequency, word_count[reversed_word])
                    result += pairs * 4
                    processed.add(reversed_word)  # Mark reverse as processed
          
            processed.add(word)
      
        # Add center palindrome if exists
        if odd_palindrome_exists:
            result += 2
          
        return result

Pitfall 2: Incorrect Handling of Self-Palindromic Words

The Problem: The variable x (or odd_palindrome_exists) accumulates the count of all palindromic words with odd frequencies, but we only need to know if at least one exists.

Example:

words = ["aa", "aa", "aa", "bb", "bb", "bb"]
# Current: x = 2 (both "aa" and "bb" have odd count)
# This doesn't affect correctness but is unnecessary

Better Approach: Use a boolean flag instead:

odd_palindrome_exists = False
for word, frequency in word_count.items():
    if word[0] == word[1]:
        if frequency % 2 == 1:
            odd_palindrome_exists = True  # Just set flag, don't accumulate
        result += (frequency // 2) * 4

Pitfall 3: Edge Case with Single Self-Palindromic Word

The Problem: Not handling the case where we only have one self-palindromic word correctly.

Example:

words = ["aa"]
# Should return 2 (can place "aa" in center)
# Make sure the logic handles this case

Verification: Ensure your solution correctly handles:

• Single palindromic word → length 2
• Multiple identical palindromic words → use pairs + one center if odd count
• Mix of palindromic and non-palindromic words → combine both strategies