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

难度: Medium

给你一个字符串数组 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⁵
words[i].length == 2
words[i] 仅包含小写英文字母。

Submission

运行时间: 91 ms

内存: 33.0 MB

class Solution:
    def longestPalindrome(self, words) -> int:
        d = Counter(words)
        r = 0
        odd = 0
        for k, v in d.items():
            if k[0] == k[1]:  # 重叠
                r += v // 2 * 4
                if v % 2:
                    odd = 1
            else:  # 非重叠
                rk = k[::-1]
                if d[rk] > 0:
                    r += min(d[k], d[rk]) * 4
                    d[k], d[rk] = 0, 0
        if odd:
            r += 2
        return r

Explain

本题的思路是利用哈希表记录每个单词出现的次数。然后遍历哈希表，对于每个键值对，分两种情况讨论： 1. 如果单词是由两个相同字母组成，比如'aa'，那么它们可以放在回文串的中间，但只能使用偶数个。每使用两个这样的单词，回文串长度增加4（两边各增加2）。如果有剩余的不能成对的单词，可以考虑放在回文串的正中间，但这种情况最多只能发生一次，因此用一个变量 odd 来标记是否已经使用过这样的单词。 2. 如果单词是由两个不同字母组成，比如'ab'，那么必须找到一个相反的单词（比如'ba'）才能一起使用，每找到一对，回文串长度增加4。为了避免重复计算，处理一对这样的单词后，将它们的计数清零。最后，如果存在可以放在中间的单词（odd为1），则回文串长度再加2。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def longestPalindrome(self, words) -> int:
        d = Counter(words)
        r = 0
        odd = 0
        for k, v in d.items():
            if k[0] == k[1]:  # 同字母组成的单词
                r += v // 2 * 4
                if v % 2:
                    odd = 1
            else:  # 不同字母组成的单词
                rk = k[::-1]
                if d[rk] > 0:
                    r += min(d[k], d[rk]) * 4
                    d[k], d[rk] = 0, 0
        if odd:
            r += 2
        return r

Explore

这样做是为了避免重复计算。当我们找到一对符合条件的单词（例如'ab'和'ba'）时，我们会将它们一起添加到回文串中，每对这样的单词可以在回文串的两边各增加2，总共增加4。一旦这两个单词被使用，它们就应该从后续计算中排除，以防再次被错误地计算。因此，将这两个单词的计数清零是确保每对单词只被计算一次的简单方法。

回文串是一种前后对称的字符串。对于由相同字母组成的单词（如'aa'），当它们成对出现时可以分别放在回文串的两端，保持对称。如果有一个单词剩余，它可以放在回文串的中心位置，但因为回文串的中心只有一个位置，所以即使有多个这样的单词剩余，也只能使用一个。这是为了维持回文串结构的整体对称性。

是的，这种计算方式适用于所有两个字母的组合。对于每对由相同字母组成的单词（如'aa', 'bb'等），可以在回文串的两端各添加一个，总共增加4。对于由两个不同字母组成的单词及其逆序单词（如'ab'和'ba'），同样每找到一对就可以在回文串的两端各添加一个，也总共增加4。这种计算方法适用于所有两字母的可能组合，因为它们都遵循相同的回文构造规则。

在回文串中，若有单词由相同字母构成且剩余单个无法成对，这个单词可以独特地放置在回文串的正中心。由于回文的对称性质，中心位置只能放置一个这样的单词。因此，虽然可能有多个这样的单词剩余，但只有一个可以被使用。使用这个单词后，它将回文串的长度增加2（因为它自身由两个字母组成）。因此，即使有多个单个剩余，odd变量的存在（标记至少有一个这样的单词剩余）只会使回文串长度最终增加2。