660. Longest Palindrome by Concatenating Two Letter Words
You are given words, an array where every element is a string of exactly two lowercase letters. Choose any subset of the elements (each array element may be used at most once, even when the same two-letter string appears several times) and glue your chosen elements together, in any order you like, into one long string.
Return the length of the longest palindrome you can build this way — a string that reads the same forwards and backwards. If no non-empty palindrome can be built, return 0.
Example 1:
Input: words = ["lc", "cl", "gg"]
Output: 6
Explanation: "lc" + "gg" + "cl" = "lcggcl", a palindrome of length 6. Every word gets used here, so nothing longer exists.
Example 2:
Input: words = ["ab", "ty", "yt", "lc", "cl", "ab"]
Output: 8
Explanation: "ty" + "lc" + "cl" + "yt" = "tylcclyt" has length 8. The two copies of "ab" have no "ba" to mirror them, so they can never join a palindrome.
Example 3:
Input: words = ["cc", "ll", "xx"]
Output: 2
Explanation: No two words mirror each other, but any single double-letter word such as "cc" is already a palindrome of length 2 on its own.
Constraints:
- 1 ≤ words.length ≤ 10⁵
- words[i].length == 2
- words[i] consists of lowercase English letters only
Hints:
A word can sit at position k from the front only if its reverse sits at position k from the back. So words pair up: "lc" with "cl", each such pair adding 4 to the length. Which words can also stand alone in the exact middle?
Count occurrences in a hash map. For a word with two different letters like "ab", you can use min(count["ab"], count["ba"]) pairs. A double-letter word like "gg" pairs with itself — floor(count/2) pairs — and if any double-letter word has an odd count, exactly one leftover copy may sit in the center for +2.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["lc", "cl", "gg"]
Expected output: 6