刷蓝桥杯刷到一道很不起眼的题：给定一个字符串，输出它字典序最大的回文子序列。看到“回文子序列”五个字，我脑子里立刻弹出最长回文子序列的区间DP板子，抄起草稿纸就开始推状态转移方程。结果推着推着越想越不对劲——这题哪儿需要DP啊，一个 O(n) 的结论就能秒杀。
这道题是典型的“脑子一热就写模板，冷静下来发现是签到题”的代表。它真正考察的不是你会不会区间DP，而是你有没有认真琢磨“字典序最大”这四个字到底意味着什么。这篇文章把题目拆解、最终结论的证明、三种语言的实现、我在实际刷题时踩过的坑，以及几个容易混的变体题型一次说清楚。备赛蓝桥杯的同学可以直接抄作业，准备面试算法题的人也可以把它当成一个“先分析性质再动手”的经典案例。
1. 题目理解与核心思路拆解
1.1 先把题面里的三个概念拆干净
子序列这个词是第一个容易含糊的点。子序列不要求字符在原串里连续，只要求先后顺序不变。比如字符串 abcde 里，ace 是子序列，aec 就不是，因为 e 在 c 前面这个顺序没法违背。回文子序列就是选出来的这些字符正着读和反着读一样。注意这里不是回文子串，子串要求连续，这题是子序列，选择灵活度大得多。
字典序则是另一个容易“感觉懂但实际用错”的概念。字符串比较字典序，是从第一个字符开始逐个往后比，谁在这一位上更大谁就赢；如果某个串先结束了，那短的这个更小。举个例子，"zz" 和 "z" 比较：第一个字符都是 z，第二个字符 "z" 没有，所以 "z" 是 "zz" 的前缀，短的更小，结论是 "zz" 更大。同理 "abc" 和 "abd" 比较，前两个字符一样，第三个 c 小于 d，所以 "abd" 更大。
把这两个概念合在一起，题目的意思就是：从原串里挑出一堆字符组成回文，允许你挑任意长度，这堆字符在原串里的顺序不变，最后在所有可能的回文里输出字典序最大的那个。注意它没有说“最长”，这一点非常关键，后面整个解题思路都围绕它展开。
1.2 为什么大多数人的第一反应会跑偏
刷过几套题的人看到“回文子序列”五个字，条件反射就是最长回文子序列（Longest Palindromic Subsequence）的区间DP，状态转移方程 dp[i][j] 从两头往中间缩，很多人的肌肉记忆比脑子还快。但这道题的关键词根本不在于“回文子序列”，而在于“字典序最大”。
字典序比较的优先级是：先比第一个字符，再比第二个字符，以此类推，长度垫底。换句话说，一个首字符很大的短串，可以轻松打败一个首字符很小但长得多的串。我用一个极简例子就能说明白：字符串 "baa"，最长回文子序列是 "aa"，长度 2，但字典序最大的回文子序列是 "b"，长度只有 1。因为 'b' 大于 'a'，哪怕 "aa" 更长，"b" 依然在字典序上完胜。
这个反例直接戳破了“长度越长越好”的直觉。出题人把“回文”和“字典序”揉在一道题里，就是等着你往DP方向钻。如果你真的写了一个区间DP求最长回文子序列，代码不仅长，复杂度还是 O(n²)，遇上 n 稍大的数据直接超时，属于方向性错误。
2. 核心定理与正确性证明
2.1 一句话结论：最大字符重复出现次数次
先把结论摆出来：设字符串 S 中字符值最大的字符为 c（竞赛环境下就是 ASCII 码最大），c 在 S 中出现的次数为 cnt，那么答案就是 cnt 个 c 拼成的字符串。
多验证几个例子巩固一下：
- s = "abc"，最大字符 'c' 出现 1 次，答案 "c"。
- s = "zabz"，最大字符 'z' 出现 2 次，答案 "zz"。虽然 "zaz" 也是回文子序列，但比较 "zz" 和 "zaz"：第一个字符都是 z，第二个字符 z 大于 a，所以 "zz" 赢。
- s = "cbbac"，最大字符 'c' 出现 2 次，答案 "cc"。有趣的是 "cbbc" 也是回文，但它在第二个字符上是 b，小于 cc 里的 c，照样输。
- s = "banana"，最大字符 'n' 出现 2 次，答案 "nn"。
看到规律没有：答案的形式是固定的，不需要搜索，不需要动态规划，甚至不需要构造“左右对称包夹”的复杂回文。整串结果就是同一个字符重复若干次，它天生就是回文。
2.2 为什么这个结论一定正确
这个结论看着简单，但要确定它是对的，得走一遍严格的逻辑，不然心里不踏实。我把证明拆成三步：
第一步，任何回文子序列 P 的第一个字符，一定是原串 S 里某个字符，所以它不可能大于全局最大字符 c。如果 P 的首字符小于 c，那 P 和 c*cnt 比较时，第一招就输了，直接出局。
第二步，如果 P 的首字符恰好等于 c，因为它是回文，尾字符也必须等于 c。每出现一个 c，都要从 S 里消耗一个 c 的配额，而 c 在 S 里总共只有 cnt 个，所以 P 里能用的 c 的数量最多是 cnt。这意味着 P 开头的连续 c 的数量不可能超过 cnt。
第三步，把 ccnt 拿出来和任意一个首字符为 c 的回文 P 逐个字符比。只要 P 在某个位置出现了一个非 c 的字符，ccnt 在这个位置依旧是 c，而 c 大于任何非 c 字符，所以 ccnt 赢下这一位。如果 P 从头到尾全是 c，那 P 的长度不可能超过 cnt，于是 P 要么等于 ccnt，要么是它的真前缀，而真前缀在字典序里更小。综合两种情况，c*cnt 稳赢。
最后确认可行性：c*cnt 本身就是回文，而且从 S 里把所有 c 按原顺序挑出来就是子序列，完全合法。所以它一定是字典序最大的回文子序列。
这段证明的本质是贪心：字典序第一优先级要求首字符必须是全局最大；首字符定了之后，下一优先级的字符也尽量大，于是把最大字符全部用上；一旦中间出现别的小字符，那一位置就比不过连续的 c，所以最优结构就是全 c。想通了这一点，整道题就转成一行统计代码。
2.3 字典序比较里的两个隐藏细节
细节一在前缀规则上。很多人会问：最大字符出现多次，为什么不全构造“c + 其他 + c”这种对称结构？因为全 c 串在字典序上碾压所有中间插字符的方案。比较 "ccc" 和 "cabac"（假设合法）：第二位 c 大于 a，瞬间胜负已分。还有人觉得“回文嘛，两头各取一个 c 就够了”，同样不对，c 重复多少次都是回文，取全所有 c 才能让前缀位置的字符尽可能大。
细节二在字符范围上。蓝桥杯题目里字符串多半是小写字母，但保不齐混进大写甚至数字。竞赛语境下的字典序统一按字符集编码比较，比如 ASCII 码顺序：数字（48~57）小于大写字母（65~90）小于小写字母（97~122）。所以 'a' 大于 'Z'。写代码时直接用 char 类型自带的比较即可，千万别自己映射成 0~25 的下标，一旦输入里混入大写或数字，映射就出偏差。
3. 代码实现与实战细节
3.1 Python 版本：五行之内搞定
Python 写这道题可以说是最轻松的：
def solve(s: str) -> str: c = max(s) # 按字符本身的 ASCII 值取最大 cnt = s.count(c) # 统计最大字符出现次数 return c * cnt s = input().strip() print(solve(s))max(s)在 Python 里直接对字符流按 ASCII 值比较，天然支持大小写和数字混合，不需要额外转换。s.count(c)再做一次线性扫描统计次数，最后用字符串乘法把 c 重复 cnt 次。整体两遍扫描，时间复杂度 O(n)，空间上答案字符串本身占 O(cnt)，其余零开销。
有个细节建议养成习惯：input()之后一定要.strip()。虽然标准测试数据通常干净，但模拟赛或自己造数据时，末尾换行符混进字符串里，max会把换行符也纳入比较，直接导致答案错乱。
3.2 C++ 版本：竞赛党的顺手写法
C++ 用 STL 一行取最大字符，一行统计次数，输出也不含糊：
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; char mx = *max_element(s.begin(), s.end()); int cnt = count(s.begin(), s.end(), mx); cout << string(cnt, mx) << '\n'; return 0; }max_element返回迭代器，解引用后就是最大字符；count统计它出现的次数；string(cnt, mx)直接构造一个由 cnt 个 mx 组成的字符串。C++ 的 char 比较底层就是整数比较，ASCII 顺序天然正确。整个程序没有任何循环手写，逻辑一目了然。注意cin >> s默认按空白字符分隔，字符串里如果有空格会截断，一般题目不会这么出，如果真遇到带空格的字符串，改用getline(cin, s)。
3.3 Java 版本：思路一致，多写几行
Java 没有字符串乘法，需要手动往 StringBuilder 里拼：
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); char mx = 0; for (char ch : s.toCharArray()) { if (ch > mx) mx = ch; } StringBuilder ans = new StringBuilder(); for (char ch : s.toCharArray()) { if (ch == mx) ans.append(ch); } System.out.println(ans); } }第一次循环找最大字符，第二次循环把所有等于最大字符的原字符顺序追加到结果里。因为所有追加的字符都相同，所以结果天然是回文。Java 的 char 也是按 Unicode 码点比较，ASCII 范围内的顺序完全等同竞赛预期。
三种语言的核心操作对比如下：
| 语言 | 取最大字符 | 统计次数 | 构造结果 | 时间复杂度 |
|---|---|---|---|---|
| Python | max(s) | s.count(c) | c * cnt | O(n) |
| C++ | max_element | count | string(cnt, mx) | O(n) |
| Java | 手写循环 | 手写循环 | StringBuilder | O(n) |
3.4 复杂度与极端数据表现
时间上只有两遍线性扫描，n 到 10^6 甚至 10^7 都毫无压力，符合蓝桥杯对“签到题”的数据量预期。空间上除了答案字符串，没有额外大数组，这在内存限制紧张的情况下也很安全。
极端情况可以脑补一下：s 全是由同一个字符组成，比如 "aaaaa"，答案就是整个原串；s 只有一个字符，答案就是它自己；s 很长但最大字符只出现一次，答案就是孤零零的一个字符。这些情况在代码里都不需要特判，逻辑天然覆盖。唯一可能让答案为空的情况是输入空串，实际比赛中不会出现，但防御性地在函数开头判断一下也不亏。
4. 常见误区与排查技巧实录
4.1 误区一：看到“回文子序列”就上区间DP
这是最高发的错误，我自己第一反应也没逃掉。最长回文子序列的 DP 方程确实经典：
dp[i][j] = dp[i + 1][j - 1] + 2 if s[i] == s[j] else max(dp[i + 1][j], dp[i][j - 1])但这道题问的根本不是长度。字符串 "baa" 用这个 DP 求最长会得到 "aa" 长度 2，而正确答案是 "b"，长度 1。如果你带着 DP 思路去跑这题，不仅答案错，代码还冗长，遇到大 n 还会超时。判断一道题该不该用 DP，先看它优化目标是什么：目标是“最长”“方案数”，DP 才有戏；目标是“字典序最大”，优先想贪心性质。
4.2 误区二：比较时把长度当第一优先级
写自定义比较函数的时候，很容易写成“先比长度，长度一样再比字典序”。这是把“最长回文子序列”和“字典序最大回文子序列”搞混的典型症状。字典序的优先级铁律是：逐字符比较在前，长度比较只在某一方是另一方前缀时才起作用。写比较器要先从索引 0 开始比字符，别一上来就if (len(a) != len(b))。
4.3 误区三：字符集范围处理想当然
有人写代码默认只有小写字母，用ord(ch) - ord('a')把字符映射成数字再算。小写字母范围内没问题，但一旦输入混入大写或数字，映射出来的相对顺序就不符合 ASCII 真实顺序。比如 'a' 的映射值是 0，'A' 也是 0，直接混淆。稳妥的办法是永远用 char 原生比较，不要人工建映射表。除非题目明确限定字符集，否则不要做任何假设。
4.4 一次真实的 WA 排查记录
我刷这道题时 WA 过两次，错得挺隐蔽。第一版代码求最大字符、统计次数都没问题，结果输出的时候我写成了c * (cnt // 2 + 1)。我的想法是：回文不是讲究对称吗，取一半左右的字符拼出来就够了吧？这个直觉放在“构造普通回文”里是合理的，但放在“全 c 串”里就是错的。比如 s = "zzzz"，cnt = 4，cnt // 2 + 1等于 3，输出 "zzz"，而正确答案明明是 "zzzz"。因为所有字符相同的时候，根本不需要“左右对称摆放”这个概念，全部取走就是最优。
第二次 WA 更低级：input()后没 strip，构造测试数据时字符串末尾带了换行符，max(s)把换行符也算进去了。换行符的 ASCII 值是 10，比任何可见字符都小，按说不会影响max的结果，但如果数据是“字符 + 空格 + 字符”这种带空格的情况，空格 ASCII 32 会干扰比较顺序。从此我养成了所有字符串一进来就 strip 的习惯，宁可多写一个方法调用，也不给数据留任何不干净的可能。
排查这类 WA 问题有个通用技巧：把答案和“最大字符 + 出现次数”打印出来逐项对。只要最大字符选择正确、次数统计正确，结果就必然正确。如果答案不对，问题几乎都出在这两个中间值上，不会出在更深的算法层面。
5. 变体拓展与备赛方法论
5.1 变体一：字典序最小的回文子序列
把“最大”换成“最小”，结论瞬间反转，而且比最大版本更反直觉。对称地分析：想让字典序最小，首字符要尽量小，于是取全局最小字符 c_min。但为什么答案是单字符 c_min，而不是把 c_min 重复 cnt 次？因为字典序里，"a" 是 "aa" 的真前缀，真前缀更小，所以单字符比多字符更小。答案就是min(s)这个字符本身。可以看出来，“最大”和“最小”的对称性并不完全一致：最小版本只输出一个字符，最大版本要输出全部最大字符。把这个对照记在心里，以后遇到类似问题能少走很多弯路。
5.2 变体二：最长回文子序列且字典序最大
如果题目改成“先要求长度最长，长度相同再比较字典序取最大”，那才轮到区间DP上场。做法是 DP 求长度，同时维护每个区间的最优字符串，或者先算长度矩阵再用路径回溯构造字典序最大的最优解。复杂度 O(n²)，n 只能支持到几千量级。这类题和原题的区别就在优化目标的优先级上：原题把字典序放第一位，长度无所谓；变体二把长度放第一位，字典序只做次级比较。刷题时看到类似的描述，第一件事就是确认“哪个指标优先”，这决定了完全不同的算法选型。
5.3 如何识别“想复杂了”的信号
刷题多了以后，我总结出几个“这题可能不用模板”的信号。第一，题面里出现“最大/最小 + 字典序”这种修饰词，这类题十有八九藏着很简单的贪心结论。第二，看数据范围，n 给到 10^6 甚至更大，基本是在暗示 O(n) 或 O(n log n) 解法，O(n²) 的 DP 可以直接排除。第三，先别急着写代码，拿几组样例在纸上手玩，故意构造“短但首字符大”的反例，很多错误直觉当场就会被戳穿。第四，写代码之前强迫自己用一句话写出答案的形式，比如“最大字符重复 cnt 次”，写不出来说明还没理解到位，写出来了代码只是顺手的活。
我个人刷题的习惯是，字符串题先不碰键盘，拿三分钟在纸上把样例改着玩。比如把 "zabz" 改成 "zzabz"，看结论从 "zz" 变成 "zzz"；再把 "baa" 改成 "baaa"，答案依旧是 "b"。多改几组，性质自然就浮出来了。这道题真正教会我的不是回文、不是字典序，而是“在套模板之前，先花三分钟想想题目到底在考什么”。有时候一行代码的结论，比十行漂亮的 DP 更值钱。
