字典序最大回文子序列：贪心解法与模板误区

备赛蓝桥杯那段时间我在刷题列表里翻到一道很不起眼的字符串题给定一个由小写字母组成的字符串输出它的字典序最大的回文子序列。题目很短样例也不难但第一次做的时候我差点按“最长回文子序列”的区间DP模板直接开写。后来发现这题其实是个典型的贪心答案甚至短得让人意外——只要找出字符串中出现过的最大字符然后把这个字符重复它出现的次数就行。这篇文章就把整个思考过程、证明细节、实现代码和一些踩坑经历完整记录下来给同样在刷题备赛的朋友做个参考。这道题适合谁看一是正在准备蓝桥杯这类算法竞赛的学生尤其容易被“回文子序列”几个字带偏直接套DP模板二是想搞懂“字典序最大/最小”这类贪心题怎么分析的人。只要清楚子序列和子串的区别理解字典序比较规则后面所有推导都顺理成章。1. 题目理解与破题思路1.1 先别急着套“最长回文子序列”模板很多人在看到“回文子序列”这五个字时第一反应就是经典的LPSLongest Palindromic Subsequence问题给你一个字符串s求最长的回文子序列长度。那个问题的标准解法是区间动态规划状态转移方程是dp[i][j] dp[i1][j-1] 2, 当 s[i] s[j] dp[i][j] max(dp[i1][j], dp[i][j-1]), 当 s[i] ! s[j]但如果照着这个模板去做“字典序最大的回文子序列”十有八九会走偏。原因很简单LPS问题的优化目标是“长度”而这道题的优化目标是“字典序”。两个目标在某些情况下是冲突的长度更长的回文子序列字典序未必更大反过来也一样。题目问的是“字典序最大的回文子序列”不是“最长的回文子序列”这两者完全是两回事。我举个最直白的例子字符串s zaz。它的所有回文子序列包括z、a、zaz、等等其中最长的是zaz长度是3。但字典序最大的回文子序列却是zz长度为2。为什么因为字典序比较时先看第一位第一位相同再看第二位。zz和zaz的第一位都是z第二位一个是z、一个是az比a大所以zz胜出。这个例子很好地说明了“最长”不等于“字典序最大”。所以拿到题目第一步不是写代码而是把优化目标看清楚。题目要求的每一个词都很关键“字典序最大的回文子序列”强调的是字典序其次是回文最后才是子序列——注意是子序列而不是子串所以允许跳字符只要保持原顺序即可。1.2 字典序最大意味着什么字典序的规则大家都很熟两个字符串从左到右逐位比较遇到第一个不同的字符谁的字符大谁就大如果前面都相同那么更长的字符串更大。这条规则给了一个非常重要的直觉首位字符的优先级远高于后面的所有字符。就好比两个人比姓氏笔画只要第一个字就能分出胜负后面写什么都不用看了。放在这道题里意思是如果一个回文子序列能以最大的字符开头那它就已经碾压了所有不以最大字符开头的回文子序列无论后者有多长。顺着这个思路问题就变成了既然要字典序最大回文子序列的第一个字符一定得是整个字符串里能取到的最大字符。那么哪个字符是整个字符串的最大字符显然就是s中字典序最大的那个字符比如zaz里的zcbaaa里的c。进一步想如果一个字符是全局最大的那它在回文子序列里出现得越多整个串的字典序是不是就越大答案是肯定的。因为不管在这个字符后面夹了多少其他字符比较到第二位时“最大字符”总是能把其他字符比下去。既然这样为什么不把这个最大字符出现的所有位置全部选上组成一个纯最大字符的串呢1.3 一个猜想的诞生把所有最大字符都拿走基于上面的分析我大胆提出一个猜想答案就是这个字符串中最大字符重复出现次数的那一串。设最大字符为c它在s中出现的次数为k那么答案就是 c 重复 k 次即 c^k。验证几个例子s abca最大字符是c出现1次答案是c。尽管有回文子序列aa、aba但都以a开头和c比第一位就输了。s zaz最大字符是z出现2次答案是zz。前面已经比较过zz比zaz还大。s cbaaa最大字符是c出现1次答案是c。哪怕aaa长度是3但第一位c a所以c赢。s babb最大字符是b出现3次答案是bbb。这个字符串中取三个b完全可以索引0、2、3形成子序列bbb显然回文也显然很大。这个猜想太简单了简单到让人怀疑这真的是一个竞赛题吗会不会有隐藏的反例后面我花了比较长时间去证明它确认没有反例。接下来就聊聊证明过程这部分才是这道题真正的营养所在。2. 贪心策略的正确性证明2.1 反证法框架要证明 c^k 是字典序最大的回文子序列需要证明两件事第一c^k 本身是一个回文子序列第二任何回文子序列都不比它大。第一件事没什么好说的c^k 是同一个字符重复k次正着读反着读完全一样所以一定是回文。而且c在s中出现了k次按顺序取出这k个c就是它的一个子序列所以可行性没问题。关键是第二件事。我采用反证法假设存在一个回文子序列P它的字典序比c^k大。先考虑P的第一个字符记作P[0]。字符P[0]的取值范围不可能超过c因为c已经是整个s中的最大字符了P是从s中取出来的P[0]当然不可能比c更大。如果P[0] c那么P和c^k比较时第一位就分出了胜负P比c^k小矛盾。如果P[0] c那就继续往后面看。由于P是回文子序列它里面出现的c总数不会超过k个因为整个s里总共只有k个c。接下来主要讨论P后面到底还能不能比c^k大。关键点来了在P中只要在某一位出现了非c字符c^k在该位置一定是c而非c字符一定小于c所以c^k立刻胜出。有人可能会问如果P从头到尾全是c呢那P就只能是最多k个c组成的串长度小于等于k当长度小于k时c^k更长根据字典序规则短串是长串的前缀时短串更小当长度等于k时P和c^k完全相同。不管哪种情况P都不大于c^k。所以结论就是任何P都无法比c^k大c^k就是字典序最大的回文子序列。证明完成。2.2 几个反直觉的小实验证明过程中最容易让人困惑的是“回文”这个限制到底有没有起作用。我做了一组小实验来验证也是写博客时常用的测试表输入字符串最大字符及出现次数字典序最大的回文子序列最长回文子序列zazz出现2次zzzazcbaaac出现1次caaaabcac出现1次caba或acababbb出现3次bbbbbbddabcd出现2次dddd从表里能看得很清楚有些情况下字典序最大的回文子序列和最长回文子序列是同一个比如babb有些情况下完全不是一个东西比如cbaaa。所以这道题绝对不能拿LPS的模板套套了就是答非所问。2.3 为什么“最长”和“字典序最大”会打架“最长”和“字典序最大”的冲突根源在于字典序比较时长度只在“前面所有字符完全相同”的情况下才起作用。一旦前面某个位置分出高低后面哪怕长出一大截也毫无意义。还是拿zaz说最长回文子序列zaz长度3前缀是za而字典序最大的zz前缀是zz第二位就把zaz比下去了。这就是为什么不能想当然地以为“先求出最长再从最长的里面挑字典序最大的”——题目的优化目标根本没让你管长度。这个认知很重要。很多竞赛新手容易犯的毛病是看到一个题目里有熟悉的关键词比如“最长”“子序列”“回文”就条件反射地开始背模板结果忽略了前面的定语是“字典序最大”。我后来复盘时总结遇到这类题先把所有修饰词圈出来想清楚优化目标到底是什么再决定用什么算法。3. 代码实现与复杂度分析3.1 最简Java实现既然答案是最大字符重复出现次数次代码量就非常少了。下面是我在竞赛环境里写的版本import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.next(); char maxChar a; for (int i 0; i s.length(); i) { char ch s.charAt(i); if (ch maxChar) { maxChar ch; } } int count 0; for (int i 0; i s.length(); i) { if (s.charAt(i) maxChar) { count; } } StringBuilder sb new StringBuilder(); for (int i 0; i count; i) { sb.append(maxChar); } System.out.println(sb.toString()); } }有人可能会问为什么maxChar初始值是a因为题目一般保证输入是小写字母所以a可以作为起始比较值。如果题目改成大小写混合或者数字字符就得换个初始值或者用数组统计的方式后面会提到。这个代码分三步走遍历一遍字符串找出最大字符再遍历一遍字符串统计最大字符出现次数输出最大字符重复相应次数的结果。两个循环都是O(n)总共O(n)时间O(1)额外空间。如果非要抠常数也可以一趟循环同时完成“找最大字符”和“统计次数”但需要处理“字符更新后旧字符的统计作废”的问题写起来反而容易错。我建议分两步走清晰、稳定、不容易出bug。3.2 Python实现与字符集通用写法如果是用Python参加比赛代码更短s input().strip() max_char max(s) cnt s.count(max_char) print(max_char * cnt)Python的max函数可以直接作用于字符串返回字典序最大的字符字符串的count方法统计出现次数字符串乘法构造重复串。三行搞定。不过这里有个隐藏前提字符串里面不能有换行符或空格所以先strip一下更稳妥。如果题目给的字符串可能包含空格比如输入一行带空格的字符串那得改用其他读入方式比如读取整行去掉首尾空白或者用replace删掉空格。再说说通用写法。假设字符集不是小写字母而是ASCII可见字符甚至包括空格那么比较好的做法是用一个数组统计每个字符的出现次数按字符值从大到小遍历找到第一个出现次数大于0的字符答案就是它重复出现次数次。Python里可以这样s input() from collections import Counter counter Counter(s) for ch in sorted(counter.keys(), reverseTrue): print(ch * counter[ch]) break思路不变只是统计方式更通用。这种写法在字符集未知的情况下更安全。3.3 复杂度与输入规模分析这道题因为贪心性质复杂度做到O(n)就是极限了不可能再低因为至少要读一遍字符串才能知道最大字符。空间上如果直接输出连额外数组都不用属于常数空间。蓝桥杯这类竞赛中字符串长度常规范围在1e5到1e6之间O(n)完全够用。相比之下如果误写了LPS的区间DPO(n^2)在长度1e5时直接爆炸连样例都过不完。所以这道题不仅仅是在考“会不会贪心”更是在考“能不能识别出不需要DP的题目”。我在后面的变体部分会聊到有些题目确实需要从LPS入手但那是优化目标叠加了长度限制之后的事不是这道题。4. 变体题型的延伸思考4.1 如果要求“先最长再字典序最大”有些题目会把优化目标改成在所有长度最大的回文子序列中输出字典序最大的那个。这个时候就不能用刚才的贪心了因为长度成了第一优先级。比如s zaz长度最大的回文子序列是zaz字典序最大的长度最大回文子序列也是zaz而不是zz因为zz长度只有2不满足“先最长”的条件。这种题目需要用区间DP求出以任意区间为单位的最长回文子序列长度dp[i][j]然后从两端向中间构造答案。构造的核心思路是如果s[i] s[j]并且dp[i][j] dp[i1][j-1] 2那么这两个字符可以同时选入答案因为它们能让长度取到最优值否则比较dp[i1][j]和dp[i][j-1]哪边能贡献更长的回文子序列就优先从哪边深入当两边长度相同时为了字典序最大需要比较下一步能够取到的字符大小选择让整体字典序更大的方向。最后一步有点绕需要结合dp表判断哪一侧最终能贡献更大的字符。我第一次写这种扩展题时在“两侧dp值相等”的分支里直接选了左边结果构造出来的串不是字典序最大。后来改成比较后续候选字符才通过。这个问题我在变体题里踩过坑后面调试实录里也会提。4.2 如果要求“字典序第K大的回文子序列”这是另一个热门变体给定字符串s和整数k求所有回文子序列中字典序第k大的那个。注意这里通常不含空串也不含重复计数的子序列或者按出现位置去重规则因题而异。这题就不能用单次贪心了得用计数构造的思路。一个可行方案是先把所有可能作为回文子序列首尾的字符按字典序从大到小排序然后逐位构造答案每尝试在当前状态下选择一个字符就统计“以这个字符为下一个字符时后面还能形成多少个回文子序列”如果数量大于等于k则确定这一位选它继续往下如果数量小于k则k减去这个数量尝试下一位字符。统计数量通常需要预处理辅助数组比如f[i][j]表示区间[i, j]内的回文子序列数量但要注意去重。这个变体比原题难一个量级如果原题是签到题这题差不多是压轴题的水平。我建议先把原题的贪心证明吃透再挑战这个扩展。4.3 如果换成“回文子串”而不是“子序列”还有一个常见的迷惑项是“子串”和“子序列”的一字之差。子串要求连续子序列要求保持顺序但可以跳字符。字典序最大的回文子串的解法完全不一样可以枚举所有回文中心用中心扩展法找回文串然后逐一比较字典序也可以用Manacher算法结合后缀数组做到更优复杂度。我见过一个很经典的坑题题目里写着“子序列”但样例里给出的是连续回文串很多人没注意就直接按子串做了结果提交时才发现完全不对。所以拿到题目先确认是“子序列”还是“子串”这一个词就能决定用贪心还是用中心扩展算法复杂度也从O(n)变成O(n^2)或更复杂。5. 常见问题与调试实录5.1 三个我在本地调试时踩过的坑第一个坑是“被最长回文子序列模板带跑”。我第一次做这道题是在题库里随机抽题看到“回文子序列”几个字就条件反射写了LPS的二维DP。代码写了大几十行跑样例时发现abca输出的是aba而不是c才意识到自己求的根本不是字典序最大。后来我把题目里“字典序最大的”这几个字高亮出来时刻提醒自己优化目标是什么。第二个坑是“贪心选两端字符”。有朋友和我讨论时提出一种做法用双指针从两端找尽量大的字符来构造回文。比如对zaz左指针找到z右指针也找到z于是构造zz看起来好像没问题。但对accca呢最大字符c出现3次索引1、2、3答案应该是ccc。如果按双指针贪心左边先选c右边也选c得到cc然后中间还能取一个c吗双指针处理时很容易漏掉中间的c。如果我直接统计全部maxChar则不会有这个问题。所以这个贪心要落在“统计全部最大字符”上而不是“找两个端点”。第三个坑是输入读取。某次模拟赛中题目输入是一整行字符串可能包含空格我用了Scanner.next()只读到了第一个单词导致字符统计不完整样例都过不了。后来改成读取整行再做处理才通过。竞赛里要养成先看输入格式的习惯究竟是“一个不含空格的字符串”还是“一行可能包含空格的文本”处理方式完全不同。5.2 赛前自测清单下面这个表格是我平时刷题时用来快速验证思路的测试用例集对这道题非常有用测试输入期望输出说明aa只有一个字符答案就是它本身aaaa两个相同字符都要取abb最大字符出现1次zazzz最大字符出现2次注意不要输出zazcbaaac最大字符出现1次长度3的aaa不是答案abcac不要被aba迷惑ddabcdd最大字符d出现2次qwertyuiopy找最大字母这里最大是y这些用例覆盖了单字符、全相同字符、最大字符出现多次但被其他字符隔开、最大字符只出现一次等情况。能在本地一次性跑通基本就稳了。5.3 从这道题带走的通用套路这道题虽然简单但方法论很有价值凡是要求“字典序最大/最小”的构造题优先考虑贪心然后必须证明贪心正确性而不是猜一个做法就提交。证明的时候抓住字典序的两个特性第一首位字符决定压倒性优势第二越靠前的位置优先级越高。只要能证明“某字符必然出现在首位”“某字符出现越多越好”题目往往就能简化到只需要数数字符次数。类似的题还有很多比如“字典序最小的字符串拼接”“删掉k个字符后字典序最小”等核心都是找到某种局部最优策略再用反证法或者交换论证法证明全局最优。这个思维习惯比背多少模板都重要。我后来再遇到新的构造题第一反应不再是“套哪个算法”而是“这个问题里哪一个选择是最关键的”。这道题带给我的收获其实挺大的。它让我重新审视了“熟悉关键词”带来的思维惯性也让我体会到竞赛题目里每个定语都可能是解题的钥匙而不是摆设。如果你也在准备蓝桥杯之类的比赛不妨多做几道这种“看似模板题、实则逆向思维”的题目做完之后认真写一篇总结进步会非常明显。