What is the primary strategy to solve Longest Palindrome by Concatenating Two Letter Words?

Use array scanning with a hash map to count word frequencies, pair each word with its reverse, and place at most one identical-letter word in the center.

Can a word be used more than once in forming the palindrome?

No, each word can be selected at most once. Pairing and central placement must respect this constraint.

Why are words with identical letters treated differently?

They can serve as the center of the palindrome, allowing maximal length without requiring a mirrored pair.

What is the time complexity of this solution?

The solution runs in O(n) time, scanning all words once and using hash lookups for reversed pairs.

What failure modes should I watch for in this problem?

Common failures include overcounting paired words, ignoring central identical-letter words, and assuming word order affects the palindrome.

#2131

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个字符串数组 words 。 words 中每个元素都是一个包含两个小写英文字母的单词。请你从 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⁵
words[i].length == 2
words[i] 仅包含小写英文字母。

lightbulb

解题思路

方法一：贪心 + 哈希表

我们先用一个哈希表 $\textit{cnt}$ 统计每个单词出现的次数。

遍历 $\textit{cnt}$ 中的每个单词 $k$ 以及其出现次数 $v$ ：

如果 $k$ 中两个字母相同，那么我们可以将 $\left \lfloor \frac{v}{2} \right \rfloor \times 2$ 个 $k$ 连接到回文串的前后，此时如果 $k$ 还剩余一个，那么我们可以先记录到 $x$ 中。
如果 $k$ 中两个字母不同，那么我们要找到一个单词 $k'$ ，使得 $k'$ 中的两个字母与 $k$ 相反，即 $k' = k[1] + k[0]$ 。如果 $k'$ 存在，那么我们可以将 $\min(v, \textit{cnt}[k'])$ 个 $k$ 连接到回文串的前后。

遍历结束后，如果 $x$ 不为空，那么我们还可以将一个单词连接到回文串的中间。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为单词的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        cnt = Counter(words)
        ans = x = 0
        for k, v in cnt.items():
            if k[0] == k[1]:
                x += v & 1
                ans += v // 2 * 2 * 2
            else:
                ans += min(v, cnt[k[::-1]]) * 2
        ans += 2 if x else 0
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) due to single-pass word counting and pairing with hash lookups. Space complexity is O(n) for the hash map storing word frequencies, independent of palindrome construction.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if you can use a hash map to find reversed word pairs efficiently.
question_mark
Consider how identical-letter words might serve as the palindrome's center.
question_mark
Be prepared to discuss linear-time pairing versus brute-force concatenation.

warning

常见陷阱

外企场景

error
Forgetting to decrement counts after pairing leads to overcounting words.
error
Not handling identical-letter words for central placement reduces palindrome length.
error
Assuming order of words matters; any order is valid for concatenation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow words of length three or more and analyze how center placement generalizes.
arrow_right_alt
Return the actual palindrome string instead of just its length.
arrow_right_alt
Count distinct palindrome arrangements instead of maximum length.

help

常见问题

外企场景

继续练习

#3035 回文字符串的最大数量 #1684 统计一致字符串的数目 #1481 不同整数的最少数目