LeetCode 2131: Longest Palindrome by Concatenating Two Letter Words Solution

Master LeetCode problem 2131 (Longest Palindrome by Concatenating Two Letter Words), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2131. Longest Palindrome by Concatenating Two Letter Words

Medium

Array Hash Table String Greedy Counting

Problem Explanation

Explanation:

To create the longest palindrome by concatenating two-letter words, we can observe that to form a palindrome, the word pairs should be the reverse of each other. Therefore, we can iterate through the words and store the frequency of each word and its reverse in a map. We can then check for word pairs that are reverse of each other and add twice the length of such pairs to the result, as we can use both the original word and its reverse in the palindrome. If there are any single occurrences of a word that is a palindrome by itself, we can add its length to the result as well.

Create a map to store the frequency of each word and its reverse.
Iterate through the words and populate the map.
For each word in the map, check if its reverse is present in the map and accumulate the length accordingly.
If there are any single palindrome words, add their length to the result.
Return the final result as the length of the longest palindrome.

Time Complexity: O(n), where n is the number of words in the input array. Space Complexity: O(n), for the map to store word frequencies.

Solution Code

class Solution {
    public int longestPalindrome(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        int result = 0;
        
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
            String reverse = new StringBuilder(word).reverse().toString();
            if (map.containsKey(reverse)) {
                result += 2 * word.length();
                map.put(reverse, map.get(reverse) - 1);
                if (map.get(reverse) == 0) {
                    map.remove(reverse);
                }
            }
        }
        
        for (String word : map.keySet()) {
            if (word.equals(new StringBuilder(word).reverse().toString())) {
                result += word.length();
                break;
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2131 (Longest Palindrome by Concatenating Two Letter Words)?

This page provides optimized solutions for LeetCode problem 2131 (Longest Palindrome by Concatenating Two Letter Words) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2131 (Longest Palindrome by Concatenating Two Letter Words)?

The time complexity for LeetCode 2131 (Longest Palindrome by Concatenating Two Letter Words) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2131 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2131 in Java, C++, or Python.

Back to LeetCode Solutions