Given a list of two-letter words, choose and arrange some of them to build the longest possible palindrome.
Problem
You are given an array of strings where each string has exactly two lowercase English letters.
You may choose any subset of the words and arrange the chosen words in any order. Concatenate them to form one string.
Return the maximum possible length of a palindrome that can be formed.
A palindrome reads the same forward and backward.
Notes
- Each word can be used at most once.
- You do not need to return the palindrome itself, only its maximum length.
- The answer is measured in total characters.
Input Format
- An array of strings
words - Each
words[i]is a two-character lowercase string
Output Format
- Return a single integer: the maximum palindrome length achievable
Constraints
words[i]consists of exactly 2 lowercase English letters- Each word may be used at most once
Example 1
Input
words = ["lc","cl","gg"]
Output
6
Explanation
We can use "lc" + "gg" + "cl" to form "lcggcl", which is a palindrome of length 6.
Example 2
Input
words = ["ab","ty","yt","lc","cl","ab"]
Output
8
Explanation
One optimal palindrome is "ty" + "lc" + "cl" + "yt", which has length 8.
Show 1 more example
Example 3
Input
words = ["cc","ll","xx"]
Output
2
Explanation
Any one of these words can be placed in the center, giving a palindrome of length 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.