Longest Palindrome by Concatenating Two Letter Words

Medium

Google

5 views

Topics:

ArraysStringsGreedy Algorithms

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 <= words.length <= 10^5
words[i].length == 2
words[i] consists of lowercase English letters.

Longest Palindrome by Concatenating Two Letter Words

Medium

Google

5 views

Topics:

ArraysStringsGreedy Algorithms

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 <= words.length <= 10^5
words[i].length == 2
words[i] consists of lowercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input array `words`?
If no palindrome can be formed, what value should be returned?
Can the same word be used twice to form a palindrome, or do we need distinct pairs?
If there are multiple palindromes that can be formed with the same maximum length, is any one of them acceptable?
Can the input array `words` be empty or contain null values?

Brute Force Solution

Approach

The brute force approach for finding the longest palindrome made from word pairs involves trying every possible combination of words. We check each combination to see if it forms a palindrome and keep track of the longest one we find. This involves a lot of checking and re-checking of different arrangements.

Here's how the algorithm would work step-by-step:

Start with the first word and try pairing it with every other word in the list.
Check if the combination of these two words forms a palindrome. Remember a palindrome reads the same forwards and backwards.
If the two-word combination is a palindrome, note its length.
Now, try combining three words. Take every possible three-word group and check if *that* is a palindrome.
Continue this process, adding more words to the group and checking if the resulting sequence is a palindrome.
Keep track of the length of the longest palindrome you've found so far.
Repeat this process, starting with the second word, then the third, and so on, so that you've tried every word as the starting point.
After you have checked all possible combinations of the words, compare the lengths of all the palindromes you found.
The longest palindrome you identified is the solution.

Code Implementation

def longest_palindrome_brute_force(words):
    longest_palindrome_length = 0
    number_of_words = len(words)

    for start_index in range(number_of_words):
        for length in range(2, number_of_words + 1):
            for i in range(number_of_words - length + 1):
                current_combination = words[i:i+length]
                combined_word = "".join(current_combination)

                # Check if the combined word is a palindrome
                if combined_word == combined_word[::-1]:

                    # Update the longest palindrome length if needed
                    longest_palindrome_length = max(longest_palindrome_length, len(combined_word))

    return longest_palindrome_length

Big(O) Analysis

Time Complexity

O(n!) – The described brute force approach attempts all possible combinations of the n words. Specifically, it considers combinations of 2 words, then 3 words, and so on up to n words. The number of such combinations grows factorially with n. Therefore the time complexity is O(n!).

Space Complexity

O(N!) – The brute force approach described involves generating all possible combinations of words. In the worst-case scenario, we might need to store all possible permutations of the input word list to explore all combinations. The number of permutations grows factorially with the number of words, which is N. Thus, the space required to store these combinations will be proportional to N!, leading to a space complexity of O(N!).

Optimal Solution

Approach

The key idea is to pair words with their reversed counterparts to form palindromes. We also handle cases where single-letter repeated words can be placed in the center of the palindrome if we have an odd number of them.

Here's how the algorithm would work step-by-step:

First, count how many times each two-letter word appears in the list.
Then, go through each word and its reversed version. If we find a word and its reverse, we use as many pairs of them as possible to build the palindrome. Each pair adds a length of four to the total palindrome length.
If a word is its own reverse (like 'aa', 'bb'), then we treat it specially. We try to include pairs of these words into our palindrome like before, but also keep track of how many of these we have left over. This is because a single word such as 'aa' can go into the very center of the palindrome.
At the end, if we have an odd number of a self-reversing word left over and we haven't used one in the center yet, add two to our total palindrome length. Only one of these can be placed in the middle.
The total length we've calculated is the length of the longest possible palindrome.

Code Implementation

def longestPalindrome(words):
    word_counts = {}
    for word in words:
        word_counts[word] = word_counts.get(word, 0) + 1

    palindrome_length = 0
    central_word_used = False

    for word in word_counts:
        reversed_word = word[::-1]

        if word in word_counts and reversed_word in word_counts:
            # Pair words with their reverses to form palindromes
            if word != reversed_word:
                pairs = min(word_counts[word], word_counts[reversed_word])
                palindrome_length += pairs * 4
                word_counts[word] -= pairs
                word_counts[reversed_word] -= pairs
            else:
                # Handle same-letter words ('aa', 'bb') carefully
                pairs = word_counts[word] // 2
                palindrome_length += pairs * 4
                word_counts[word] -= pairs * 2

                # Check if we can use a single same-letter word in the center
                if word_counts[word] == 1:
                    # Use center word if not yet used.
                    if not central_word_used:
                        palindrome_length += 2
                        central_word_used = True

    return palindrome_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of n two-letter words to count the frequency of each word using a hash map (or similar data structure), which takes O(n) time. Then, it iterates through the unique words in the hash map, and for each word, it performs a constant-time lookup for its reversed version. Thus, the reversed-pair check takes O(m) where m is the number of unique words which is <= n. The logic for single letter repeated words also take constant time during that same pass. Since m <= n, the dominant operation is the initial frequency count, resulting in a time complexity of O(n).

Space Complexity

O(1) – The primary space usage stems from counting the occurrences of each two-letter word. This can be done using a hash map (or frequency table) which, in the worst case, would store counts for all possible two-letter words. Since there are a limited number of possible two-letter word combinations (26 * 26 = 676, assuming only lowercase English letters), the space used by this hash map is constant and independent of the input array's size, N. The other variables used, such as the palindrome length and counters, occupy constant space. Thus, the overall space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no palindrome can be formed.
Array with a single two-letter word	If the single word is a palindrome (e.g., 'aa'), store it for possible center; otherwise, return 0.
Array contains only palindromic two-letter words (e.g., ['aa', 'bb', 'aa'])	Handle by counting pairs and allowing at most one unpaired palindromic word as the center.
Array contains no palindromes at all	The algorithm should correctly identify that there's no center and still find all reverse pairs.
Maximum array size with varied words (stress test)	Use efficient data structures (hash maps) to ensure the solution scales reasonably.
Words longer or shorter than two letters (invalid input)	The problem statement specifies two-letter words; input validation at the beginning can ensure correct input.
Array contains duplicate pairs	The frequency map will account for multiple pairs and handle them correctly.
Integer overflow if the length becomes too long	Ensure the data type used to store the length is sufficiently large (e.g., long long in C++ or equivalent in other languages) to avoid overflow issues.