Problem

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Examples

Example 1:

Input:
words = ["lc","cl","gg"]
Output:
 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input:
words = ["ab","ty","yt","lc","cl","ab"]
Output:
 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input:
words = ["cc","ll","xx"]
Output:
 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Solution

Method 1 - Using Map

To solve the problem of creating the longest possible palindrome from a list of strings, we can use the following approach:

  1. Group Words:
    • Group the words based on whether they mirror themselves (e.g., “aa”, “bb”) or have a reversal counterpart in the list (e.g., “ab” and “ba”).
  2. Count Pairs:
    • For words that have a reversal counterpart, count the number of such pairs.
    • For words that are self-mirrored, determine how many such words can pair up and if there is any leftover that can stay in the middle for the palindrome.
  3. Calculate Length:
    • Each pair of mirrored words contributes twice their length to the total palindrome length.
    • Each pair of reversal counterparts will contribute their entire length as they add symmetry from both ends.
  4. Handle Odd Palindrome:
    • If there is any leftover self-mirrored word, it can be placed in the center, contributing its full length to the palindrome.

Code

Java
public class Solution {
    public int longestPalindrome(String[] words) {
        HashMap<String, Integer> map = new HashMap<>();
        int ans = 0;
        int middle = 0;
        
        for (String word : words) {
            String reverse = new StringBuilder(word).reverse().toString();
            if (map.getOrDefault(reverse, 0) > 0) {
                ans += 4;
                map.put(reverse, map.get(reverse) - 1);
            } else {
                map.put(word, map.getOrDefault(word, 0) + 1);
            }
        }
        
        for (String word : map.keySet()) {
            if (word.charAt(0) == word.charAt(1) && map.get(word) > 0) {
                middle = 2;
                break;
            }
        }
        
        return ans + middle;
    }
}
Python
class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        count = Counter(words)
        ans = 0
        middle = 0
        
        for word in list(count.keys()):
            reverse = word[::-1]
            if word == reverse:
                # handle words that are mirror images of themselves
                ans += (count[word] // 2) * 2 * 2
                if count[word] % 2 == 1:
                    middle = 1
            else:
                pairs = min(count[word], count[reverse])
                ans += pairs * 4
                count[word] -= pairs
                count[reverse] -= pairs
        
        return ans + middle * 2

Complexity

  • ⏰ Time complexity: O(n), where n is the number of words in the list. This includes iterating through the list and counting pairs.
  • 🧺 Space complexity: O(n), primarily for storing counts of words in a dictionary.