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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

方法一：贪心 + 哈希表

思路与算法

根据回文串的定义，回文串可以由奇数或者偶数个 words 中的单词拼接而成，但必须满足以下条件：

  • 如果数量为奇数，那么位于正中间的单词必须是回文字符串（即两个字符相等）；

  • 每个单词和反转后对应位置的单词必须互为反转字符串。

根据上面的两个条件，我们可以得出构造最长回文串的规则：

  • 对于两个字符不同的单词，需要尽可能多的成对选择它和它的反转字符串（如有）；

  • 对于两个字符相同的单词，需要尽可能多的成对选择该单词；

  • 如果按照上述条件挑选后，仍然存在未被选择的两个字符相同的单词（此时该字符串只可能有一个未被选择，且该字符串一定在 words 中出现奇数次），我们可以任意选择一个。

因此，我们用哈希表统计 words 中每个单词的出现次数。随后，我们遍历哈希表的所有元素，并用 res 维护可能构成回文字符串的最长长度，同时用初值为 false 的布尔变量 mid 判断是否存在可以作为中心单词的、出现奇数次的回文单词。在遍历到字符串 word 时，我们首先求出它反转后的字符串 rev，此时根据 word 与 rev 的关系，有以下两种情况：

  • word} \not = \textit{rev，此时我们需要统计两者在 words 出现次数的最小值，即为成对选择的最多数目。假设此时对数为 n，则其对最长回文字符串贡献的字符长度为 4n，我们将 res 加上对应值；

  • word} = \textit{rev，此时可以构成的对数为 \lfloor m / 2 \rfloor，即对最长回文字符串贡献的字符长度为 4\lfloor m / 2 \rfloor，我们同样将 res 加上对应值。除此以外，我们还需要判断 word 的出现次数 m 是否为奇数：

    • 如果 m 为奇数，则存在可以作为中心单词的剩余回文单词，我们将 mid 置为 true；

    • 如果 m 为偶数，则不存在可以作为中心单词的剩余回文单词，我们不改变 mid 的取值。

最后，我们根据 mid 的取值，判断最长回文串是否含有中心单词。如果 mid 为 true，则代表含有，我们将 res 加上 2；反之则没有，我们不进行任何操作。

最后，我们返回 res 作为最长回文串的长度。

细节

在遍历哈希表中的每个单词时，为了避免重复计算成对选择的单词，我们只在 word 的字典序大于等于 rev 时更新 res。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        unordered_map<string, int> freq;   // 单词出现次数
        for (const string& word: words) {
            ++freq[word];
        }
        int res = 0;   // 最长回文串长度
        bool mid = false;   // 是否含有中心单词
        for (const auto& [word, cnt]: freq) {
            // 遍历出现的单词，并更新长度
            string rev = string(1, word[1]) + word[0];   // 反转后的单词
            if (word == rev) {
                if (cnt % 2 == 1) {
                    mid = true;
                }
                res += 2 * (cnt / 2 * 2);
            }
            else if (word > rev) {   // 避免重复遍历
                res += 4 * min(freq[word], freq[rev]);
            }
        }
        if (mid) {
            // 含有中心单词，更新长度
            res += 2;
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        freq = Counter(words)   # 单词出现次数
        res = 0   # 最长回文串长度
        mid = False   # 是否含有中心单词
        for word, cnt in freq.items():
            # 遍历出现的单词，并更新长度
            rev = word[1] + word[0]   # 反转后的单词
            if word == rev:
                if cnt % 2 == 1:
                    mid = True
                res += 2 * (cnt // 2 * 2)
            elif word > rev:   # 避免重复遍历
                res += 4 * min(freq[word], freq[rev])
        if mid:
            # 含有中心单词，更新长度
            res += 2
        return res

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组 words 的长度。即为遍历统计数组各个元素的出现次数以及遍历哈希表计算最长回文串长度的时间复杂度。

  • 空间复杂度：O(\min(n, |\Sigma|^2))，即为哈希表的空间开销。哈希表的大小受到两方面限制：

    • 哈希表的大小小于等于两字母单词的数量，即 O(|\Sigma|^2)；
    • 哈希表的大小小于等于 words 中单词数量，即 O(n)。
 Comments
On this page
2131-连接两字母单词得到的最长回文串