学习目标

• 能根据字符出现次数判断哪些字符可以成对放入回文串。
• 使用贪心策略计算最长回文串的长度。
• 解释为什么最多只能额外放置一个奇数次字符作为中心。

前置知识

• 字符串遍历与字符计数。
• 回文串的对称结构。
• C++ 标准输入输出和数组或哈希表。

问题描述

给定一个只包含大写字母和小写字母的字符串 s，请返回使用这些字符可以构造出的最长回文串长度。构造时区分大小写，例如 "Aa" 不能配成一对。

每种字符可以使用若干个完整字符：除回文串中心最多一个字符外，其他字符都必须成对出现。

输入格式

输入一行字符串 s。

输出格式

输出一个整数，表示最长回文串的长度。

约束

• 1 ≤ s.length ≤ 2000。
• s 只包含大小写英文字母。
• 不需要处理不符合约束的输入。

示例

示例 1

输入：

abccccdd

输出：

7

示例 2

输入：

a

输出：

1

思路提示

统计每个字符出现的次数。对于出现 count 次的字符，先取出 count / 2 * 2 个，保证它们可以对称放置；如果还有任意字符剩下奇数个，就可以把其中一个放在回文串中心。

注意：中心位置只能增加一次。字符 A 和 a 是两种不同的字符，必须分别计数。

复杂度要求

• 时间复杂度：O(n)，其中 n 是字符串长度。
• 额外空间复杂度：O(Σ)，其中 Σ 是字符集大小。

运行与评分

在本 Lab 目录执行：

make doctor
make run
make score

如果没有 Make，也可以在仓库根目录执行：

pnpm lab:run -- labs/chapter-13/exercise/E-13-02-longest-palindrome --target student

参考实现可以使用下面的命令验证：

pnpm lab:verify -- labs/chapter-13/exercise/E-13-02-longest-palindrome --no-color

完成清单

• 正确读取整行字符串并输出最长回文串长度。
• 每种字符只把最大偶数部分计入成对字符。
• 存在奇数次字符时只额外使用一个中心字符。
• 保持大写字母和小写字母区分，并通过全部测试。

思考与复盘

1. 为什么每种字符都可以先安全地取出尽可能多的成对字符？
2. 如果字符串中有多个字符出现奇数次，为什么不能把它们都放进同一个回文串的中心？
3. 如果题目改为只允许使用完整字符且不允许丢弃字符，问题会发生什么变化？

题目来源

本题对应 LeetCode 409「最长回文串」：https://leetcode.cn/problems/longest-palindrome/。