2131. Longest Palindrome by Concatenating Two Letter Words

MediumGreedyArrayHash TableStringCounting

Problem Description

In this problem, we have an array of strings called words. Each string is composed of exactly two lowercase English letters. Our objective is to construct the longest possible palindrome by selecting and concatenating some elements from the given words array. We are allowed to use each element only once.

A palindrome is defined as a sequence that reads the same both forwards and backwards. For example, "radar" and "level" are palindromes.

We are required to return the length of the longest palindrome that can be created. If no palindromes can be formed using the elements of words, the function should return 0.

Intuition

To solve this problem, we need to find pairs of words that can contribute to the palindrome. There are two distinct scenarios to consider:

Matching pairs: A pair of words where one is the reverse of the other (e.g., "ab" and "ba"). These can be placed symmetrically on either side of the palindrome.
Palindrome pairs: Words that are palindromes in themselves (e.g., "aa", "bb"). They can be placed in the middle of the palindrome or paired with themselves to be placed symmetrically.

Our strategy is to count the frequency of each word and then iterate over our count dictionary to calculate the contribution of each word to the longest palindrome. For each word, we check:

If it's a palindrome pair (the word is the same when reversed), we can use it in pairs in the palindrome (e.g., "cc"..."cc" in the middle). The count of these words can only contribute in even numbers for both halves of the palindrome. If there’s an odd count, one instance can be placed in the middle.
If it's a matching pair (word and the reverse are different), we can use as many of these pairs as the minimum count of the word and its reversed pair.

An additional consideration is that we can only place at most one palindrome word in the very center of the palindrome.

The primary steps of the solution include:

Counting each word's occurrence using a Counter structure for efficient lookup.
Iterating over the unique words and calculating their potential contribution to the palindrome length.
If possible, adding an extra pair of letters if we have leftover palindrome pairs to maximize the palindrome length.

Based on this logic, the provided solution code computes the longest possible palindrome efficiently.

Learn more about Greedy patterns.

Solution Approach

The solution employs a Counter from Python's collections module to efficiently count the occurrences of each word in the words array. A Counter is essentially a dictionary where each key is an element from the input array and its corresponding value is the number of times that element appears.

We then iterate through the items in the Counter to determine how each word can contribute to the length of the palindrome. The code consists of a few key steps:

Initialize two accumulators: ans represents the length of the potential palindrome, and x represents the count of center elements that appear an odd number of times.
For every unique word k and its count v in the counter:
- If the word is a palindrome itself (the same forwards and backwards, i.e., k[0] == k[1]):
  - The half-count of such words v // 2 contributes to both halves of the palindrome. So the contribution would be double the half-count times two v // 2 * 2 * 2.
  - If there's an odd count of a palindrome word (v & 1), we increment x, because it means we have an instance of this word that can potentially be placed in the center of the palindrome.
- If the word is not a palindrome and has a complementary word that is its reverse (k[::-1]) in the array:
  - The contribution of such pairs is limited by the lesser count of the pair, hence we use min(v, cnt[k[::-1]]) * 2.
After iterating through all words, we check if x is greater than 0, which would mean that we have at least one word that can be placed at the center. If it's possible, add 2 to ans to account for the center element.
Return ans as the length of the longest palindrome.

In summary, by using a counter to track word frequencies and understanding the two types of pairs (matching and palindrome pairs), we can efficiently calculate the maximum possible palindrome length. The solution is quite elegant as it minimizes the amount of work necessary by directly computing the contribution each word can make to the final palindrome structure without having to explicitly build the palindrome.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach using an array of strings words = ["ab", "ba", "aa", "cc", "cc", "aa"].

Following the solution approach, we first use a Counter to count occurrences:

ab: 1
ba: 1
aa: 2
cc: 2

Next, we iterate over these counts and calculate how they contribute to the potential palindrome:

The word "ab" has a count of 1. By checking its reverse, we find "ba" also has a count of 1. They can be used as a pair to contribute 2 to the palindrome length ("ab" + "ba" or "ba" + "ab" on either side).
The word "aa" is a palindrome itself and has a count of 2. This means it can contribute twice its half-count (which is 1) to both halves of the palindrome, adding 4 to the length ("aa" + "aa" on either side).
The word "cc" is also a palindrome and has a count of 2. It contributes another 4 to the length like "aa" ("cc" + "cc" on either side).

Since both "aa" and "cc" have even counts, there's no additional contribution to the center, so we have x = 0.

Adding together the contributions we get 2 (from "ab" and "ba") + 4 (from "aa") + 4 (from "cc") equals 10, which is the length of the longest palindrome that can be created.

Lastly, since there is no extra odd-count palindrome word to place in the center (x is 0), we don't add anything more to ans.

Therefore, the length of the longest palindrome that can be created from the given words array is 10.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def longestPalindrome(self, words: List[str]) -> int:
5        # Create a count of all words
6        word_count = Counter(words)
7        length_of_palindrome = central_letter_pair_count = 0
8      
9        # Counter.items() contains pairs of (word, count)
10        for word, count in word_count.items():
11            # Check if the word is a pair of identical letters, like "aa"
12            if word[0] == word[1]:
13                # Count of such word pairs that can be used as the central part of the palindrome
14                central_letter_pair_count += count % 2
15                # Add the count (rounded down to the nearest even number) times 2 to the length
16                length_of_palindrome += (count // 2) * 4
17            else:
18                # For other pairs, add the minimum count of the pair and its reverse pair to the length
19                length_of_palindrome += min(count, word_count[word[::-1]]) * 2
20      
21        # If there are pairs of identical letters, we could place exactly one in the center of the palindrome
22        length_of_palindrome += 2 if central_letter_pair_count else 0
23      
24        return length_of_palindrome
25

1class Solution {
2    public int longestPalindrome(String[] words) {
3        // Create a map to store the frequency of each word
4        Map<String, Integer> wordCount = new HashMap<>();
5        // Loop through the array of words to populate the map with word counts
6        for (String word : words) {
7            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
8        }
9
10        // Initialize variables to store the length of palindrome formed and a flag for center character allowance
11        int palindromeLength = 0, singleCenter = 0;
12
13        // Iterate over the map entries to calculate the maximum possible palindrome length
14        for (Map.Entry<String, Integer> entry : wordCount.entrySet()) {
15            String word = entry.getKey();
16            String reversedWord = new StringBuilder(word).reverse().toString();
17            int count = entry.getValue();
18
19            // If the word is the same as its reversed version and has two identical characters,
20            // it can potentially be a center of the palindrome
21            if (word.charAt(0) == word.charAt(1)) {
22                // Check if there's an odd count, if so one instance can be used as a center
23                singleCenter += count % 2;
24                // Add the even part into the palindrome length (doubled, as palindromes are symmetric)
25                palindromeLength += (count / 2) * 2 * 2;
26            } else {
27                // If the word is not its own reversed, pair it with its reverse occurrence count
28                palindromeLength += Math.min(count, wordCount.getOrDefault(reversedWord, 0)) * 2;
29            }
30        }
31
32        // If there is at least one single center word, add 2 to the length for the center character of palindrome
33        palindromeLength += singleCenter > 0 ? 2 : 0;
34
35        // Return the total calculated palindrome length
36        return palindromeLength;
37    }
38}
39

1class Solution {
2public:
3    int longestPalindrome(vector<string>& words) {
4        // The 'wordCount' map will store each unique word and its frequency.
5        unordered_map<string, int> wordCount;
6      
7        // Count the occurrence of each word in the input vector.
8        for (auto& word : words) {
9            wordCount[word]++;
10        }
11      
12        // Initialize the length of the longest palindrome to 0 and a variable 'middleInserted' to check for the middle character in palindrome.
13        int longestLength = 0, middleInserted = 0;
14      
15        // Traverse each entry in the map to calculate the max length of palindrome.
16        for (auto& [key, value] : wordCount) {
17            // Create the reverse of the current word.
18            string reversedKey = key;
19            reverse(reversedKey.begin(), reversedKey.end());
20          
21            // Check if the word consists of identical letters (e.g., "gg", "aa").
22            if (key[0] == key[1]) {
23                // If it's a palindrome by itself, increment 'middleInserted' if an odd count.
24                middleInserted += value & 1;
25
26                // Add to the 'longestLength' an even number of this word (pairs).
27                longestLength += (value / 2) * 2 * 2; // multiply by 2 - two letters per word, another multiply by 2 - forming pairs.
28            } else if (wordCount.count(reversedKey)) {  // If the reversed word is also in the map.
29                // Use only the minimum count from the word and its reversed counterpart for a palindrome.
30                longestLength += min(value, wordCount[reversedKey]) * 2; // multiply by 2 because each word forms a pair with its reverse.
31            }
32        }
33
34        // Adjust the 'longestLength' with 2 extra letters if the middle character can be inserted to make the palindrome longer.
35        if (middleInserted > 0) {
36            longestLength += 2;
37        }
38      
39        return longestLength; // Return the longest palindrome length calculated.
40    }
41};
42

1let wordCount: Record<string, number> = {};
2
3function longestPalindrome(words: string[]): number {
4    // Clear the word count for each invocation
5    wordCount = {};
6
7    // Count the occurrence of each word in the input array.
8    words.forEach(word => {
9        wordCount[word] = (wordCount[word] || 0) + 1;
10    });
11
12    // Initialize the length of the longest palindrome to 0
13    // and a variable to check for the middle character in a palindrome.
14    let longestLength: number = 0;
15    let middleInserted: number = 0;
16
17    // Traverse each entry in the map to calculate the max length of palindrome.
18    Object.entries(wordCount).forEach(([key, value]) => {
19        // Create the reverse of the current word.
20        const reversedKey: string = key.split('').reverse().join('');
21      
22        // Check if the word consists of identical letters (e.g., "gg", "aa").
23        if (key[0] === key[1]) {
24            // If it's a palindrome by itself, increment 'middleInserted' if an odd count.
25            middleInserted += value & 1;
26
27            // Add to the 'longestLength' an even number of this word (pairs).
28            longestLength += (value >> 1) * 4; // bitwise shift used for integer division by 2 and multiply by 4 for pairs
29        } else if (wordCount[reversedKey] !== undefined) { // If the reversed word also exists.
30            // Use only the minimum count from the word and its reversed counterpart for a palindrome.
31            longestLength += Math.min(value, wordCount[reversedKey]) * 2;
32          
33            // After pairing, remove the entries so they are not re-counted
34            wordCount[reversedKey] = 0;
35            wordCount[key] = 0;
36        }
37    });
38
39    // Adjust the 'longestLength' with 2 extra letters if the middle character can be inserted to make the palindrome longer.
40    if (middleInserted > 0) {
41        longestLength += 2;
42    }
43  
44    return longestLength; // Return the longest palindrome length calculated.
45}
46

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by a few factors:

Constructing the Counter object from the words list. This operation has a time complexity of O(n), where n is the number of words in the input list, since it has to count the occurrences of each unique word.
Iterating over the items in the counter. In the worst case, each word is unique, so this operation could iterate up to n times.
For each word, we may check for its reverse in the counter. This is a constant time operation O(1) given the nature of hashmaps (dict in Python).

Therefore, the time complexity of the loop is also O(n).

Adding the contributions from these operations, the overall time complexity is O(n). There is no nested iteration or operations that would increase the order of complexity beyond linear.

Space Complexity

The space complexity of the code is primarily affected by the storage requirements of the Counter object:

The Counter object stores elements as keys and their counts as values. In the worst case, every word in words is unique, which means the Counter will store n keys and values. Hence, space complexity for the Counter is O(n).
The integer variables ans and x use a constant amount of space, O(1).

So, the overall space complexity of the function is O(n) due to the space taken by the Counter object. All other variables only contribute a constant space overhead which does not depend on the input size.

Therefore, the final space complexity is O(n).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: