2131. 连接两字母单词得到的最长回文串

题目

给你一个字符串数组 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] 仅包含小写英文字母。

思路

思路比较简单，做出来也不难，但时间是否可以更优，代码逻辑是否够优雅就是问题了，具体思路看下面代码。

代码

自己写的（不够优雅、慢一些）

直觉上，对于每一个字符串，找一下对应的反转的字符串（记作）是否存在（使用一个哈希表记录字符串出现的次数），如果存在那么可以凑成一对回文，将答案加，将哈希表中次数减；如果不存在，将加入哈希表。最后因为可能存在本身就对称的可以放在中间使长度再加，那么最后再遍历一下哈希表，看是否存在一个对称的，存在的话，加，然后直接（因为最多放一个）

这种思路比较好想，也不绕，不用在循环主体考虑是否对称，但是时间比较慢，因为是逐步累加计算的，每找到一对都要更新和，比较费时，可以优化。

class Solution {
    public int longestPalindrome(String[] words) {
        int n = words.length;
        Map<String, Integer> map = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            StringBuilder re = new StringBuilder(words[i]).reverse().toString();
            if (map.containsKey(re)) {
                ans += 4;
                map.put(re, map.get(re) - 1);
                if (map.get(re) == 0) {
                    map.remove(re);
                }
            } else {
                map.put(words[i], map.getOrDefault(words[i], 0) + 1);
            }
        }
        for (String str : map.keySet()) {
            if (str.charAt(0) == str.charAt(1)) {
                ans += 2;
                break;
            }
        }
        return ans;
    }
}

官解版本

优化的思路也不难想，先统计出来每个字符串出现的次数，然后遍历哈希表，对于相同的回文对可以一次性更新，另外也可以不用更新，因此会比较快。

class Solution {
    public int longestPalindrome(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int ans = 0;
        // 如果最后有一个对称字符串可以放在中间，那么mid为2，否则为0
        int mid = 0;
        for (String word : map.keySet()) {
            int cnt = map.get(word);
            // word本身对称，比如"aa"
            if (word.charAt(0) == word.charAt(1)) {
                // 先算成对的，两个为一对，那么有cnt/2对，一对长度为4，所以再乘4，最后对答案的贡献就是cnt / 2 * 4
                ans += cnt / 2 * 4;
                // 因为"aa"这样对称的字符串最后可以放在中间再贡献两个长度，因此如果cnt为奇数时，就表示还有一个单独的字符串可以放在中间
                // mid要么是0要么是2，只能增加一次
                if (mid == 0 && cnt % 2 == 1) {
                    mid = 2;
                }
            } else {
                // word本身不对称，比如"fa"
                String re = new StringBuilder(word).reverse().toString();
                // 如果对称的存在，比如"af"存在
                if (map.containsKey(re)) {
                    // 这里比较巧妙，当前遍历"fa"，ans只增加"fa"贡献的长度，"af"的等遍历到了再增加
                    // 如果在遍历"fa"时就把"af"的贡献也加上了，那么需要想办法标记已经增加过了，可以修改re的value值或者干脆移除re，但一是增加了额外处理，二是语法上不支持遍历map时对其进行修改
                    // 增加的长度为贡献字符串个数*2，其中个数为Math.min(cnt, map.get(re))
                    ans += Math.min(cnt, map.get(re)) * 2;
                }
            }
        }
        return ans + mid;
    }
}