点击获取AI摘要

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

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

问题分析

给定一个包含若干长度为 2 的小写字母单词的数组 words。需要从中选取若干个单词，按任意顺序拼接成一个回文串（正读和反读相同），每个单词最多只能使用一次。目标是让拼接得到的回文串长度尽可能长，返回最终回文串的长度。

所有单词长度恒为 2，记为 $w_1w_2$ 。
回文串可以分成 两种贡献来源：
- 互为逆序的不同单词成对放在回文串两侧，例如 “ab” 与 “ba” 各贡献 2 个字符放在左侧和右侧，共计 4。
- 自身即回文的单词放在中间，例如 “gg”、“aa”，如果两两配对放在两侧，每对依旧贡献 $4$ ；如果剩下一个用于回文中心，则贡献 $2$ 。
要保证每个单词至多使用一次，且对于自身回文的单词只能最多取一个放在“中心位置”。

因此，思路是通过哈希表统计每个单词的出现次数，再针对上述两种情况进行贪心匹配。

算法思路

统计单词频次
使用 Counter（哈希表）统计数组 words 中每个二字母单词的出现次数，记为 $\text{cnt}[w]$ 。
遍历哈希表配对
对于哈希表中的每个单词 word，令 $c = \text{cnt}[ \text{word} ]$ ：
- 令 rev = word[::-1]，即取单词的逆序。
- 情况 A：word == rev（自身回文）
  - 将可以成对放在两侧的数量计算为 $\left\lfloor \frac{c}{2} \right\rfloor$ ，每对贡献长度 $4$ ；更新 $\text{cnt}[word] -= 2 \times \left\lfloor \frac{c}{2} \right\rfloor$ 。
  - 若此时 $\text{cnt}[word] \bmod 2 = 1$ 且尚未使用中心位置（用布尔变量 used_center 标记），则取一个放在回文中心，贡献长度 $2$ ，并将 used_center = True，同时 $\text{cnt}[word] -= 1$ 。
- 情况 B：word != rev（与逆序单词匹配）
  - 若逆序单词 rev 也在哈希表中且 $\text{cnt}[rev] > 0$ ，则可取对数 $p = \min(\text{cnt}[word], \text{cnt}[rev])$ ，每对贡献 $4$ ，更新 $\text{cnt}[word] -= p$ 、 $\text{cnt}[rev] -= p$ 。
贪心原则
- 对于互为逆序的不同单词，尽量成对使用，保证两侧对称。
- 对于自身回文的单词，先尽可能两两配对放在两侧，再考虑是否把剩余的一个放在中心，以获得最大长度。
返回结果
最终累计的 total_length 即为最长回文串的长度。如果无法拼出任何回文，则 total_length 为 0。

时间复杂度

统计频次：遍历 words 长度为 $n$ 的数组， $O(n)$ 。
遍历哈希表：哈希表至多包含 $n$ 个不同二字母单词，遍历亦为 $O(n)$ 。
对每个单词的倒序操作由于固定长度 2，可视为常数时间 $O(1)$ 。

综上，整体时间复杂度为

$O(n) + O(n) = O(n).$

代码分解

将上述思路拆解为以下几个步骤：

引入必要模块

1 2	from collections import Counter from typing import List

统计哈希表
1
cnt = Counter(words)
初始化变量
1
2
total_length = 0
used_center = False

遍历哈希表进行匹配

for word, c in cnt.items():
    if c == 0:
        continue
    rev = word[::-1]
    if word == rev:
        # 处理自身回文
        ...
    else:
        # 处理与逆序单词配对
        ...

处理自身回文逻辑

# pairs = c // 2
total_length += pairs * 4
cnt[word] -= pairs * 2
if cnt[word] > 0 and not used_center:
    total_length += 2
    used_center = True
    cnt[word] -= 1

处理互为逆序逻辑

if rev in cnt and cnt[rev] > 0:
    pair_count = min(cnt[word], cnt[rev])
    total_length += pair_count * 4
    cnt[word] -= pair_count
    cnt[rev] -= pair_count

返回累计长度
1
return total_length

代码实现

from collections import Counter
from typing import List

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        # 1. 统计每个单词出现次数
        cnt = Counter(words)
        
        total_length = 0       # 最终回文串长度
        used_center = False    # 是否已使用过“中心回文单词”
        
        # 2. 遍历哈希表进行配对
        for word, c in cnt.items():
            if c == 0:
                # 如果已经被配对消耗完，直接跳过
                continue
            
            rev = word[::-1]  # 单词逆序
            
            if word == rev:
                # 情况 A：自身就是回文，例如 "gg"
                # 先两两配对放在两侧
                pairs = c // 2
                total_length += pairs * 4   # 每对各占两侧 2 + 2
                cnt[word] -= pairs * 2
                
                # 如果剩下一个且尚未使用中心，则放在中间
                if cnt[word] > 0 and not used_center:
                    total_length += 2
                    used_center = True
                    cnt[word] -= 1
            else:
                # 情况 B：与逆序单词匹配，例如 "ab" 与 "ba"
                if rev in cnt and cnt[rev] > 0:
                    pair_count = min(cnt[word], cnt[rev])
                    total_length += pair_count * 4
                    cnt[word] -= pair_count
                    cnt[rev] -= pair_count
        
        # 3. 返回最终回文串长度
        return total_length