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

Longest Palindrome by Concatenating Two Letter Words

Number: 2237

Difficulty: Medium

Paid? No

Companies: Google, Apple, Databricks

Problem Description

Given an array of two-letter words, determine the length of the longest palindrome that can be formed by selecting some of these words and concatenating them in any order. Each word can be used at most once. If forming any palindrome is impossible, return 0.

Key Insights

  • Pair words with their reverse (e.g., "ab" with "ba") to form a palindrome.
  • Handle words that are palindromic by themselves (like "gg" or "aa") differently; they can be used in pairs and one extra can be placed in the center.
  • Use a hash map (or dictionary) to count frequencies of each word.
  • For non-palindromic word pairs, consider each pair only once to avoid double counting.
  • For self-palindromic words, count how many pairs can be used and whether an extra word can be placed in the middle to maximize length.

Space and Time Complexity

Time Complexity: O(n), where n is the number of words, since we iterate through the list and perform constant time operations per word.
Space Complexity: O(n), to store counts of words in the hash map.

Solution

The approach is to count the occurrences of each word using a hash map. For each word:

  • If the word is not self-palindromic, check if its reverse exists and form pairs by considering the minimum count between the word and its reverse.
  • If the word is self-palindromic, form as many pairs as possible (using count // 2) and note if there is any word left; you can use one extra self-palindromic word as the center of the palindrome. Finally, compute the total length by multiplying the number of words used by 2, since each word contributes 2 characters.

Code Solutions

# Python solution
from collections import Counter

class Solution:
    def longestPalindrome(self, words):
        # Count the frequency of each word
        word_count = Counter(words)
        length = 0    # Total words used count (each adds 2 letters)
        center_used = False
        
        for word, count in list(word_count.items()):
            reverse = word[::-1]  # Get the reverse of the current word
            
            if word == reverse:
                # For words that are palindromic themselves (e.g. "gg")
                pairs = count // 2
                length += pairs * 2  # Each pair adds 2 words (4 letters)
                # If an extra word exists and center is not used, add one word in the center
                if count % 2 == 1 and not center_used:
                    length += 1
                    center_used = True
            else:
                # For words that are not self-palindromic.
                if reverse in word_count:
                    # We only count each pair once, so use minimum and then set the reverse count to 0.
                    pair_count = min(count, word_count[reverse])
                    length += pair_count * 2    # each pair contributes two words
                    # Set reverse count to 0 to avoid double counting later.
                    word_count[reverse] = 0
        return length * 2  # Each word is of length 2

# Example usage:
# sol = Solution()
# print(sol.longestPalindrome(["lc", "cl", "gg"]))  # Output: 6
← Back to All Questions