目标
给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
回文串 指的是从前往后和从后往前读一样的字符串。
示例 1：
输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。示例 2：
输入：words = ["ab","ty","yt","lc","cl","ab"]
输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。示例 3：
输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。说明：
- 1 <= words.length <= 10^5
- words[i].length == 2
- words[i] 仅包含小写英文字母。
思路
有一个字符串数组 words，其元素字符个数为 2，求从中选择任意元素组成回文串的最大长度。
统计每个元素的出现次数，如果数组元素的两个字符不同，要组成回文只能左右对称，计算对称的元素对数 cnt，长度为 cnt * 4。如果元素的两个字符相同，它可以全部放到中间，为了使回文最长，当出现更长的相同字符元素时，可以将原来放中间的个数 centerCnt，放到对称的两边，centerCnt / 2 * 4。
代码
/**
* @date 2025-05-25 1:03
*/
public class LongestPalindrome2131 {
public int longestPalindrome(String[] words) {
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
char a = word.charAt(0);
char b = word.charAt(1);
map.merge(a + String.valueOf(b), 1, Integer::sum);
}
int res = 0;
int centerCnt = 0;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
char a = key.charAt(0);
char b = key.charAt(1);
if (a == b) {
Integer cnt = entry.getValue();
if (cnt % 2 == 1) {
res += centerCnt / 2 * 4;
centerCnt = cnt;
} else {
res += cnt / 2 * 4;
}
} else {
int cnt = Math.min(entry.getValue(), map.getOrDefault(b + String.valueOf(a), 0));
res += cnt * 4;
}
entry.setValue(0);
}
return res + centerCnt * 2;
}
}
性能
