日期: 2025 年 5 月 25 日

目标

给你一个字符串数组 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;
    }

}

性能