2131.连接两字母单词得到的最长回文串：分类讨论(贪心)

【LetMeFly】2131.连接两字母单词得到的最长回文串：分类讨论(贪心)

力扣题目链接：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 <= 105
• words[i].length == 2
• words[i] 仅包含小写英文字母。

解题方法：分类讨论

解题思路

有的字符串自对称(如aa)，有的字符串非自对称(如ab)。

非对称的字符串只能和和它对称的字符串放到对称的位置(如ab**ba)，而自对称的字符串不但能和自身放到对称的位置(如aa**aa)也可以自身单独放到最中间的位置(如**aa**)。

但是，在整个最终构造的字符串中，自对称放字符串放到最中间的至多只能有一个。

具体方法

使用一个哈希表或26x26大小的数组统计每种字符串的出现次数。

使用变量i从0到25遍历：

首先对于自对称的字符串(如aa)，假设有$n$个，则可以拿$\lfloor\frac{n}2\rfloor$对放到对称的位置。若$n$为奇数，则还可以保留一个放到最中间的位置。

接着使用变量j从i+1到26遍历，可以互相放到对称位置的字符串一共有$\min(times[i][j], times[j][i])$对。

最终，由于中间位置最多只能放一对，所以$(对称对数\times2+中间个数)\times 2$即为所求。

时空复杂度分析

• 时间复杂度$O(N^2)$
• 空间复杂度$O(N\log N)$

AC代码

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-05-25 23:39:17
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-25 23:54:22
 */
package main

func longestPalindrome(words []string) int {
    times := make([][]int, 26)
    for i := range times {
        times[i] = make([]int, 26)
    }
    for _, word := range words {
        times[word[0] - 'a'][word[1] - 'a']++
    }
    side, mid := 0, 0
    for i := range times {
        side += times[i][i] / 2 * 2
        mid |= times[i][i] % 2
        for j := i + 1; j < 26; j++ {
            side += min(times[i][j], times[j][i]) * 2
        }
    }
    return (side + mid) * 2
}

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-05-25 23:39:17
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-26 00:04:19
 */
class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        int cnt[26][26] = {0};
        for (string& word : words) {
            cnt[word[0] - 'a'][word[1] - 'a']++;
        }
        int ans = 0, middle = 0;
        for (int i = 0; i < 26; i++) {
            ans += cnt[i][i] / 2 * 2;
            middle |= cnt[i][i] % 2;
            for (int j = i + 1; j < 26; j++) {
                ans += min(cnt[i][j], cnt[j][i]) * 2;
            }
        }
        return (ans + middle) * 2;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-05-25 23:39:17
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-25 23:47:11
'''
from typing import List

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        cnt = [[0] * 26 for _ in range(26)]
        for word in words:
            cnt[ord(word[0]) - ord('a')][ord(word[1]) - ord('a')] += 1
        ans = middle = 0
        for i in range(26):
            ans += cnt[i][i] // 2 * 2
            middle |= cnt[i][i] % 2
            for j in range(i + 1, 26):
                ans += min(cnt[i][j], cnt[j][i]) * 2
        return (ans + middle) * 2

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-05-25 23:39:17
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-25 23:51:33
 */
class Solution {
    public int longestPalindrome(String[] words) {
        int[][] times = new int[26][26];
        for (String word : words) {
            times[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;
        }
        int side = 0, middle = 0;
        for (int i = 0; i < 26; i++) {
            side += times[i][i] / 2 * 2;
            middle |= times[i][i] % 2;
            for (int j = i + 1; j < 26; j++) {
                side += Math.min(times[i][j], times[j][i]) * 2;
            }
        }
        return (side + middle) * 2;
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

（最近CSDN发文时咋不出默认封面图了）