##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2131.html

# 2131. Longest Palindrome by Concatenating Two Letter Words (Medium)

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:6Explanation: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:8Explanation: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:2Explanation: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.

**Companies**:

Google

**Related Topics**:

Array, Hash Table, String, Greedy, Counting

**Similar Questions**:

## Solution 1. Hash Table

```
// OJ: https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int longestPalindrome(vector<string>& A) {
unordered_map<string, int> m;
for (auto &s : A) m[s]++;
int ans = 0, even = 0, odd = 0;
for (auto &[s, cnt] : m) {
if (s[0] == s[1]) {
if (cnt % 2) odd = 1;
even += cnt - cnt % 2;
} else {
string r(rbegin(s), rend(s));
if (m.count(r)) {
ans += min(cnt, m[r]) * 2;
cnt = 0;
}
}
}
return (ans + even + odd) * 2;
}
};
```