409. 最长回文串

🟢   🔖  贪心 哈希表 字符串  🔗 力扣 LeetCode

题目

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive , for example, "Aa" is not considered a palindrome.

Example 1:

Input: s = "abccccdd"

Output: 7

Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"

Output: 1

Explanation: The longest palindrome that can be built is "a", whose length is 1.

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.

题目大意

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的最长的 回文串 的长度。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入: s = "abccccdd"

输出: 7

解释:

我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入: s = "a"

输出: 1

解释： 可以构造的最长回文串是"a"，它的长度是 1。

提示:

• 1 <= s.length <= 2000
• s 只由小写 和/或 大写英文字母组成

解题思路

我们要从给定字符串 s 中构造出最长的回文串。

• 回文串具有对称性，字符成对分布，例如 'aa' 或 'bb'，因此每找到一对字符，就可以添加这两个字符到回文串的两端，贡献长度 +2。
• 最后如果还有未配对的字符，可以选一个放在回文串的中间，这样仍然是有效的回文串，贡献长度 +1。

具体算法如下：

1. 使用一个 Set 数据结构来记录字符是否已配对。

   • 遍历字符串 s，对每个字符：
     • 如果字符已经存在于 Set 中，说明找到一对相同字符，将这对字符贡献的长度 +2，然后从 Set 中删除该字符（表示这对字符已被使用）。
     • 如果字符不存在于 Set 中，将该字符添加到 Set 中，表示它当前未找到配对。

2. 遍历结束后，Set 中剩余的字符都是未配对的字符：

   • 如果 Set 中有字符（set.size > 0），说明可以选择一个字符放在回文串的中间，贡献长度 +1。

3. 返回最终计算得到的最长回文串的长度。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，遍历一遍字符串 s。
• 空间复杂度：O(k)，其中 k 是字符的种类数（最多为 52 个大小写字母），Set 最多存储 k 个字符。

代码

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
	let set = new Set(); // 用于记录字符是否配对
	let maxLength = 0;

	for (let char of s) {
		if (set.has(char)) {
			// 发现配对的字符，贡献长度 +2
			maxLength += 2;
			set.delete(char); // 移除已配对的字符
		} else {
			// 未找到配对，将字符加入 Set
			set.add(char);
		}
	}

	// 如果还有未配对的字符，可以放一个字符在回文串中间
	if (set.size > 0) {
		maxLength += 1;
	}

	return maxLength;
};

相关题目

题号	标题	题解	标签	难度	力扣
266	回文排列 🔒		位运算 哈希表 字符串	🟢	🀄️ 🔗
2131	连接两字母单词得到的最长回文串		贪心 数组 哈希表 2+	🟠	🀄️ 🔗
2384	最大回文数字		贪心 哈希表 字符串 1+	🟠	🀄️ 🔗