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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Palindrome by Concatenating Two Letter Words

Difficulty: Medium

Problem Description

You are given an array of strings words. Each element of words consists of two lowercase English letters. 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.

Key Insights

  • A palindrome can be formed by pairing words that are reverses of each other (e.g., "ab" with "ba").
  • Words that are the same (e.g., "cc") can be used in pairs to contribute to the palindrome.
  • At most one word that is itself a palindrome can be placed in the center of the final palindrome.
  • The solution involves counting occurrences of each word and its reverse.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a hash table (or dictionary) to count the occurrences of each word. The algorithm involves the following steps:

  1. Count the occurrences of each two-letter word in the input array.
  2. For each unique word, check if its reverse exists in the hash table.
  3. For each pair of words (a word and its reverse), we can take the minimum count of both to form pairs contributing to the palindrome.
  4. Keep track of any palindrome words that can be used in the center.
  5. Sum the lengths of the formed pairs and add 2 for any center palindrome word found.

This approach ensures we efficiently calculate the maximum length of the palindrome that can be constructed.

Code Solutions

from collections import Counter

def longestPalindrome(words):
    count = Counter(words)
    length = 0
    center_used = False

    for word in count:
        reverse_word = word[::-1]
        if word == reverse_word:  # word is a palindrome itself
            length += (count[word] // 2) * 2  # add pairs of itself
            if count[word] % 2 == 1:
                center_used = True  # we can use one in the center
        elif reverse_word in count:
            length += min(count[word], count[reverse_word]) * 2

    if center_used:
        length += 2  # we can add one central palindrome word

    return length
← Back to All Questions