Problem Informations

• Problem Index: 2131
• Problem Link: Longest Palindrome by Concatenating Two Letter Words
• Topics: Array, Hash Table, String, Greedy, Counting

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.

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".

Constraints:

• $1 \leq \text{words.length} \leq 10^5$
• $\text{words}[i].length == 2$
• $\text{words}[i]$ consists of lowercase English letters.

Intuition

The problem asks for constructing the longest possible palindrome using the given array of two-letter words. A palindrome reads the same forwards and backwards, which suggests that the order of concatenation should ensure symmetry. The key insight here is that each word can potentially be paired with its reverse to contribute to the palindrome’s length. Therefore, the solution should systematically identify these pairs. Additionally, words composed of identical letters (like “aa”) can potentially stand alone in the center of the palindrome.

Approach

The approach follows a systematic process to construct the longest palindrome by making use of a frequency array to store occurrences of each two-letter word and its reverse. Here’s how the algorithm is structured:

1. Initialize Variables:

   • A variable ans is initialized to zero to track the total length of the palindrome being constructed.
   • A frequency vector of size 676 (since there are 26x26 possible combinations of two letters) is initialized to zero to count the occurrences of each possible two-letter combination.

2. Index Calculation:

   • For each word, calculate an index that represents it and its reverse. The index is computed based on the position of characters in the English alphabet to uniquely map each pair and its reverse to positions in the frequency vector.

3. Pair Matching:

   • For each word, check if its reverse already exists by looking it up in the frequency array using the calculated indices.
   • If such a reverse exists, it means a pair can be formed to contribute to the palindrome. In this case, decrease the reverse pair’s count in the frequency array and increase ans by 4 (each pair contributes 4 to the length).
   • If no reverse is found, increment the position for its reverse in the frequency array.

4. Center Check for Identical Pairs:

   • After processing all words, loop through the frequency vector to ascertain the presence of any identical letter pairs (e.g., “aa”, “bb”).
   • If any such pair is found, one can be used as a central element in the palindrome, contributing an additional two to the palindrome length (ans).

5. Return Result:

   • Finally, return the calculated length ans, which represents the longest possible palindrome using the given words.

This approach ensures an efficient solution with a time complexity of $O(n)$, where $n$ is the number of words, since it involves iterating over the words and performing constant-time operations using indexing and the frequency array.

Code

C++

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        int len = words.size();  // Get the number of words
        int ans = 0;  // Initialize the length of the longest palindrome
        vector<short> frequency(676, 0);  // Vector to count frequency of each pair
        
        for (int i = 0; i < len; i++) {
            // Calculate the index for the current word and its reverse
            int forwardIndex = (words[i][0] - 'a') * 26 + (words[i][1] - 'a');
            int reverseIndex = (words[i][1] - 'a') * 26 + (words[i][0] - 'a');
            
            // Check if the reverse pair exists
            if (frequency[forwardIndex] > 0) {
                frequency[forwardIndex]--;  // Reduce the count of forwardIndex
                ans += 4;  // Add 4 to the palindrome length because a pair and its reverse add 4 in length
            } else {
                frequency[reverseIndex]++;  // Store the current pair as reverse index
            }
        }
        
        // Check for any presence of pairs like "aa", where both characters are the same
        for (int i = 0; i < 26; i++) {
            if (frequency[27 * i] > 0) {
                ans += 2;  // Add 2 to the result for a single center piece
                break;  // Only one single pair can be used as the center
            }
        }
        
        return ans;  // Return the length of the longest palindrome possible
    }
};

Python

class Solution:
    def longestPalindrome(self, words):
        len_words = len(words)  # Get the number of words
        ans = 0  # Initialize the length of the longest palindrome
        frequency = [0] * 676  # List to count frequency of each pair
        
        for i in range(len_words):
            # Calculate the index for the current word and its reverse
            forwardIndex = (ord(words[i][0]) - ord('a')) * 26 + (ord(words[i][1]) - ord('a'))
            reverseIndex = (ord(words[i][1]) - ord('a')) * 26 + (ord(words[i][0]) - ord('a'))
            
            # Check if the reverse pair exists
            if frequency[forwardIndex] > 0:
                frequency[forwardIndex] -= 1  # Reduce the count of forwardIndex
                ans += 4  # Add 4 to the palindrome length because a pair and its reverse add 4 in length
            else:
                frequency[reverseIndex] += 1  # Store the current pair as reverse index
        
        # Check for any presence of pairs like "aa", where both characters are the same
        for i in range(26):
            if frequency[27 * i] > 0:
                ans += 2  # Add 2 to the result for a single center piece
                break  # Only one single pair can be used as the center
        
        return ans  # Return the length of the longest palindrome possible

Complexity

• Time complexity: $O(n)$

  The time complexity of this algorithm is $O(n)$, where $n$ is the length of the input vector words. This is because we iterate over the words vector once in the main loop to calculate the frequency of the string pairs, which takes $O(n)$ time. The subsequent loop that checks for pairs of the form “aa” iterates a fixed number of times (26 times), which is constant with respect to the input size, so it does not affect the overall time complexity.

• Space complexity: $O(1)$

  The space complexity of this algorithm is $O(1)$, which is constant space. We use a fixed-size vector frequency of size 676 (since there are 26 * 26 possible pairs of lowercase letters), regardless of the size of the input words. The storage used by the frequency vector does not scale with the input size and is therefore considered constant space complexity.