# Longest Palindrome by Concatenating Two Letter Words
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words)
Canonical: https://scaleengineer.com/dsa/problems/longest-palindrome-by-concatenating-two-letter-words
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
**Companies:** [Databricks](https://scaleengineer.com/companies/databricks)
---
## Problem
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 <= 105`
* `words[i].length == 2`
* `words[i]` consists of lowercase English letters.

# Approaches
## Brute-force with Nested Loops
This approach iterates through the list of words to find pairs of words that are reverses of each other (e.g., "ab" and "ba"). It uses a nested loop structure to compare each word with every other word. To avoid re-using words, a boolean `used` array tracks which words have been included in the palindrome. After finding all non-palindromic pairs, it makes a second pass to handle palindromic words (e.g., "gg") to form the center of the final palindrome.
**Time:** O(N^2) due to the nested loops for finding pairs, where N is the number of words. · **Space:** O(N) for the `used` array. The map for palindromes stores at most 26 unique words.
**Pros:** Conceptually simple and easy to follow the logic.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on most online judges for the given constraints.
### Explanation
The algorithm works by first pairing up all non-palindromic words with their reverses. It uses a nested loop, where the outer loop picks a word `words[i]` and the inner loop searches for its reverse `words[j]` in the rest of the array. An auxiliary boolean array `used` is maintained to ensure each word is used at most once. For every pair found (e.g., "lc" and "cl"), the length of the palindrome is increased by 4, and both words are marked as used. After this `O(N^2)` process, a separate pass is made over the remaining (unused) words. The frequencies of the unused palindromic words (e.g., "gg") are counted. These are used to further extend the palindrome. Even counts of a palindromic word form pairs, and an odd count allows one to be placed in the center.

```java
class Solution {
    public int longestPalindrome(String[] words) {
        int n = words.length;
        boolean[] used = new boolean[n];
        int length = 0;

        // Handle non-palindromic pairs
        for (int i = 0; i < n; i++) {
            if (used[i] || words[i].charAt(0) == words[i].charAt(1)) {
                continue;
            }
            String reversed = "" + words[i].charAt(1) + words[i].charAt(0);
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && words[j].equals(reversed)) {
                    length += 4;
                    used[i] = true;
                    used[j] = true;
                    break;
                }
            }
        }

        // Handle palindromic words
        java.util.Map<String, Integer> palindromeCounts = new java.util.HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!used[i] && words[i].charAt(0) == words[i].charAt(1)) {
                palindromeCounts.put(words[i], palindromeCounts.getOrDefault(words[i], 0) + 1);
            }
        }

        boolean centerAdded = false;
        for (int count : palindromeCounts.values()) {
            length += (count / 2) * 4;
            if (count % 2 == 1) {
                centerAdded = true;
            }
        }

        if (centerAdded) {
            length += 2;
        }

        return length;
    }
}
```
### Algorithm
1. Initialize `length = 0` and a boolean array `used` of the same size as `words`, all set to `false`.
2. Iterate through `words` with an outer loop from `i = 0` to `n-1`.
3. If `words[i]` is already used, skip it.
4. Check if `words[i]` is a palindrome (e.g., "gg"). If so, skip it for now; we'll handle these in a separate pass.
5. If `words[i]` is not a palindrome (e.g., "lc"), find its reverse (e.g., "cl").
6. Start an inner loop from `j = i + 1` to `n-1`.
7. If `words[j]` is not used and is the reverse of `words[i]`, we've found a pair.
8. Add 4 to `length`, mark both `words[i]` and `words[j]` as used, and break the inner loop to find a pair for the next word.
9. After the nested loops, handle the palindromic words. Create a frequency map for all unused words that are palindromes.
10. Iterate through this frequency map. For each palindromic word with count `c`, add `(c / 2) * 4` to `length`. If any palindromic word has an odd count, we can place one in the center, so we note that a center piece is available.
11. If a center piece is available, add 2 to the total `length`.
12. Return `length`.

## Using a HashMap for Frequency Counting
A more efficient approach is to first count the occurrences of each word using a HashMap. This avoids the `O(N^2)` search for pairs. After counting, we can iterate through the unique words in the map to build the palindrome based on the counts of words and their reverses.
**Time:** O(N) where N is the number of words. Building the map takes O(N), and iterating through the unique words takes O(U), where U <= N. · **Space:** O(U) to store the frequency map, where U is the number of unique words. Since U is at most 676, this can be considered O(min(N, 676)).
**Pros:** Significantly faster than the nested loop approach with a linear time complexity.; Efficient for large inputs and passes the given constraints.
**Cons:** Uses a HashMap which might have a slight overhead compared to a simple array due to hashing and potential collisions.
### Explanation
This approach begins by populating a `HashMap` with the frequencies of all words in the input array. This takes linear time, `O(N)`. Then, it iterates through the map's entries. For each word, it checks if it's a palindrome (e.g., "gg") or not (e.g., "lc").
- If `word` is a palindrome, we calculate how many pairs can be formed from its count (`count / 2`) and add `(count / 2) * 4` to the total length. If the count is odd, a single word is left over, which can be a potential center for the final palindrome. A flag `centerFound` is set to true in this case.
- If `word` is not a palindrome, we find its reverse. To prevent double-counting, we only process the pair if the current word is lexicographically smaller than its reverse. We find the number of pairs we can form (`min(count(word), count(reverse))`) and add `pairs * 4` to the length.
Finally, if `centerFound` is true, we add 2 to the total length for the central word.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestPalindrome(String[] words) {
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
            counts.put(word, counts.getOrDefault(word, 0) + 1);
        }

        int length = 0;
        boolean centerFound = false;

        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            String word = entry.getKey();
            int count = entry.getValue();

            if (word.charAt(0) == word.charAt(1)) { // Palindromic word
                length += (count / 2) * 4;
                if (count % 2 == 1) {
                    centerFound = true;
                }
            } else if (word.charAt(0) < word.charAt(1)) { // Non-palindromic, check one direction
                String reversed = "" + word.charAt(1) + word.charAt(0);
                if (counts.containsKey(reversed)) {
                    int reversedCount = counts.get(reversed);
                    int pairs = Math.min(count, reversedCount);
                    length += pairs * 4;
                }
            }
        }

        if (centerFound) {
            length += 2;
        }

        return length;
    }
}
```
### Algorithm
1. Create a `HashMap<String, Integer>` to store the frequency of each word in the input array.
2. Initialize `length = 0` and a boolean `centerFound = false`.
3. Iterate through each `word` and its `count` in the HashMap.
4. **Case 1: The word is a palindrome** (e.g., "gg").
   - We can form `count / 2` pairs. Each pair (`"gg" ... "gg"`) adds 4 to the length. So, add `(count / 2) * 4` to `length`.
   - If `count` is odd, one "gg" is left over. This can be the center of our palindrome. We set `centerFound = true`.
5. **Case 2: The word is not a palindrome** (e.g., "lc").
   - Find its reverse (e.g., "cl").
   - To avoid double-counting (processing "lc" and then "cl" again), we only consider pairs where the word is lexicographically smaller than its reverse.
   - If the reverse word exists in the map, find the number of pairs we can form, which is `min(count of word, count of reverse_word)`.
   - Each pair adds 4 to the length. Add `min_count * 4` to `length`.
6. After iterating through all unique words, if `centerFound` is true, it means we have an unused palindromic word that can be placed in the center. Add 2 to the final `length`.
7. Return `length`.

## Optimized Frequency Counting with a 2D Array
This is the most optimized approach. Since the words are composed of two lowercase English letters, the number of possible unique words is small and fixed (`26 * 26 = 676`). We can use a 2D array `int[26][26]` as a direct-access frequency map, which is faster than a HashMap. `counts[i][j]` stores the frequency of the word formed by the i-th and j-th letters of the alphabet.
**Time:** O(N + A^2), where N is the number of words and A is the alphabet size. Since A is a constant (26), the complexity is O(N). · **Space:** O(A^2) for the `counts` array, where A is the alphabet size (26). This is constant space, O(1).
**Pros:** Most efficient in terms of both time and space.; Avoids HashMap overhead by using direct array indexing.; Uses constant extra space, as the array size is fixed and does not depend on the input size N.
**Cons:** The logic might be slightly less intuitive at first glance compared to using a HashMap with string keys.
### Explanation
This approach leverages the constraint that words are made of two lowercase English letters. Instead of a generic HashMap, it uses a `26x26` integer array as a specialized frequency map. `counts[i][j]` stores the count of the word formed by the i-th and j-th letters. The first step is to iterate through the input `words` and populate this 2D array, which takes `O(N)` time.

After counting, the palindrome length is calculated by iterating through the `counts` array. 
- For non-palindromic pairs (where `i != j`), we iterate `i` from 0 to 25 and `j` from `i+1` to 25 to avoid double counting. The number of pairs formed by `(i,j)` and `(j,i)` is `min(counts[i][j], counts[j][i])`, contributing `4 * pairs` to the length.
- For palindromic words (where `i == j`), we iterate `i` from 0 to 25. The number of pairs is `counts[i][i] / 2`, contributing `(counts[i][i] / 2) * 4` to the length. If `counts[i][i]` is odd, a single word can be a center, so a flag is set.
Finally, if a center was found, 2 is added to the total length.

```java
class Solution {
    public int longestPalindrome(String[] words) {
        int[][] counts = new int[26][26];
        for (String word : words) {
            counts[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;
        }

        int length = 0;
        boolean centerFound = false;

        // Handle non-palindromic pairs
        for (int i = 0; i < 26; i++) {
            for (int j = i + 1; j < 26; j++) {
                int pairs = Math.min(counts[i][j], counts[j][i]);
                length += pairs * 4;
            }
        }

        // Handle palindromic words
        for (int i = 0; i < 26; i++) {
            int count = counts[i][i];
            length += (count / 2) * 4;
            if (count % 2 == 1) {
                centerFound = true;
            }
        }

        if (centerFound) {
            length += 2;
        }

        return length;
    }
}
```
### Algorithm
1. Initialize a 2D array `counts[26][26]` with all zeros.
2. Iterate through the input `words`. For each `word`, increment the corresponding cell in the `counts` array. For a word `w`, the cell is `counts[w.charAt(0)-'a'][w.charAt(1)-'a']`.
3. Initialize `length = 0` and a boolean `centerFound = false`.
4. **Handle non-palindromic pairs**: Iterate with `i` from 0 to 25 and `j` from `i+1` to 25. This ensures we consider each pair of distinct letters `(i, j)` only once.
   - Find the number of pairs for words `(char(i), char(j))` and `(char(j), char(i))`. This is `min(counts[i][j], counts[j][i])`.
   - Add `min_count * 4` to `length`.
5. **Handle palindromic words**: Iterate with `i` from 0 to 25.
   - Let `count = counts[i][i]`.
   - Add `(count / 2) * 4` to `length`.
   - If `count` is odd, it means we have a leftover palindromic word for the center. Set `centerFound = true`.
6. If `centerFound` is true, add 2 to `length`.
7. Return `length`.

# Solutions
### Java

```java
class Solution {
public
  int longestPalindrome(String[] words) {
    Map<String, Integer> cnt = new HashMap<>();
    for (var w : words) {
      cnt.put(w, cnt.getOrDefault(w, 0) + 1);
    }
    int ans = 0, x = 0;
    for (var e : cnt.entrySet()) {
      var k = e.getKey();
      var rk = new StringBuilder(k).reverse().toString();
      int v = e.getValue();
      if (k.charAt(0) == k.charAt(1)) {
        x += v & 1;
        ans += v / 2 * 2 * 2;
      } else {
        ans += Math.min(v, cnt.getOrDefault(rk, 0)) * 2;
      }
    }
    ans += x > 0 ? 2 : 0;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestPalindrome(vector<string> &words) {
    unordered_map<string, int> cnt;
    for (auto &w : words)
      cnt[w]++;
    int ans = 0, x = 0;
    for (auto &[k, v] : cnt) {
      string rk = k;
      reverse(rk.begin(), rk.end());
      if (k[0] == k[1]) {
        x += v & 1;
        ans += v / 2 * 2 * 2;
      } else if (cnt.count(rk)) {
        ans += min(v, cnt[rk]) * 2;
      }
    }
    ans += x ? 2 : 0;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestPalindrome(self, words: List[str]) -> int: cnt = Counter(words) ans = x = 0 for k, v in cnt . items(): if k[0] == k[1]: x += v & 1 ans += v // 2 * 2 * 2 else: ans += min(v, cnt[k[:: - 1]]) * 2 ans += 2 if x else 0 return ans

```