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

greedy, hash table, https://leetcode.cn/problems/longest-palindrome-by-concatenating-two-letter-words/

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

Greedy

from collections import Counter
from typing import List

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        count = Counter(words)
        res = 0
        central_used = False  # 标记是否已经用了一个自回文字符串作为中心
        
        for word in count:
            reversed_word = word[::-1]
            if word == reversed_word:
                # 处理自回文字符串
                pairs = count[word] // 2
                res += pairs * 4
                count[word] -= pairs * 2
                # 如果还有剩余且尚未使用中心位置，则可以作为中心增加2长度
                if count[word] > 0 and not central_used:
                    res += 2
                    central_used = True
            else:
                # 处理互为逆序的字符串对
                if reversed_word in count:
                    pairs = min(count[word], count[reversed_word])
                    res += pairs * 4
                    count[word] -= pairs
                    count[reversed_word] -= pairs
                    
        return res