字典序最大回文子序列：贪心结论而非区间DP模板

刷蓝桥杯刷到一道很不起眼的题给定一个字符串输出它字典序最大的回文子序列。看到“回文子序列”五个字我脑子里立刻弹出最长回文子序列的区间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 范围内的顺序完全等同竞赛预期。三种语言的核心操作对比如下语言取最大字符统计次数构造结果时间复杂度Pythonmax(s)s.count(c)c * cntO(n)Cmax_elementcountstring(cnt, mx)O(n)Java手写循环手写循环StringBuilderO(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 的映射值是 0A 也是 0直接混淆。稳妥的办法是永远用 char 原生比较不要人工建映射表。除非题目明确限定字符集否则不要做任何假设。4.4 一次真实的 WA 排查记录我刷这道题时 WA 过两次错得挺隐蔽。第一版代码求最大字符、统计次数都没问题结果输出的时候我写成了c * (cnt // 2 1)。我的想法是回文不是讲究对称吗取一半左右的字符拼出来就够了吧这个直觉放在“构造普通回文”里是合理的但放在“全 c 串”里就是错的。比如 s zzzzcnt 4cnt // 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 更值钱。