上周末这场周赛Q2 的 3746 题叫“等量移除后的字符串最小长度”名字听着绕其实核心就一句话给你一个字符串每次操作移除两个不同字符问最终字符串最短能剩多长。这题我一开始想复杂了把它当成字符串模拟题又是双端队列又是指针结果越绕越远。停下手写了几组例子之后才反应过来这题和字符本身没什么关系只和每种字符出现的次数有关。这篇复盘我会把从读题到提交通过的完整思考过程写下来包括公式推导、代码实现、以及我在周赛里踩过的三个坑适合所有在字符串最小化类题目上容易想复杂的朋友。1. 先想清楚等量移除到底在考什么1.1 把操作翻译成“不同颜色球的抵消”题目里说的“等量移除”放到这道题的场景里最常见的理解就是每次同时拿走两个字符而且这两个字符不能相同。我在读题时第一时间把这个操作翻译成了“不同颜色球的抵消”假设字符串里每个字符是一种颜色的球黑色代表 a白色代表 b红色代表 c。操作就是每次从这堆球里挑两个颜色不同的球扔掉最后问这堆球最少还能剩几个。这个翻译看起来简单但它直接决定了整个问题的建模方向。字符串本身是有顺序的可是题目从头到尾没有说只能删除相邻字符也没有说只能删除首尾字符等于每一次操作你都可以随便挑两个位置。这种自由度意味着字符在原始字符串里的位置信息是完全没有用的你根本不需要维护“剩余串长什么样”只需要知道每种字符还剩多少个。本质上这是一个多重集合问题不是一个序列问题。我举个例子s aabbcc 和 s abcabc它们的位置分布完全不一样但作为多重集合是一样的都是每种字符出现两次那么它们能做到的最终结果也完全一样都是消到空。很多选手卡在这一步就是因为脑子里还残留着“字符串必须按顺序处理”的惯性。1.2 直接模拟为什么容易翻车比赛时我最初的想法是维护一个频次哈希表每次取出现次数最多的两个不同字符各减一直到剩不下两个不同字符为止。这个思路本身不是错的但是如果真用数组加循环来找最大值每操作一次都要扫一遍所有字符最坏情况下字符串长度到 10^5操作次数接近 n/2复杂度直接变成 O(n^2)肯定会超时。更别提有人会想用队列维护剩余串、模拟删除后还要拼接那复杂度更难看。周赛里 Q2 这类题目最大的陷阱就是你一旦走进“模拟删除过程”的胡同就很难出来。而实际上如果题目只要求输出长度不要求输出最终的字符串大多数情况下都存在一个绕过模拟的数学结论。这个结论不需要你真正执行操作只需要统计频次、算一个式子。1.3 状态压缩只关心出现次数把所有字符的数量压缩成一个频次数组之后问题就变成一个纯组合问题。假设字符串总长度是 n出现次数最多的那个字符的频次是 mx那么其他所有字符的总数是 n - mx。接下来你只需要回答一个问题当“最大频次的字符”和“其余所有字符”数量失衡时会发生什么均衡时又会发生什么。这两个分支就是整道题的解题钥匙。下面一节我会把两种情况分别推一遍最后合并成一个公式。2. 最小长度公式从哪来失衡与均衡的两种结局2.1 失衡情况一个字符占了半壁江山如果某一个字符的出现次数超过总数的一半也就是 2 * mx n情况就很特殊。假设这个字符是 c。除了 c 之外的所有字符总数是 n - mx比 c 本身还要少。每次操作如果想让剩下的长度尽量小最有效的做法是拿一个 c 和一个非 c 字符抵消。非 c 字符最多只有 n - mx 个所以最多只能进行 n - mx 次这样的抵消。抵消完之后c 还剩mx - (n - mx) 2 * mx - n这些剩下的字符全是 c再也找不到第二个不同字符和它配对操作就停止了。所以失衡情况下的答案是 2 * mx - n。举个例子s aaabb总长 5a 出现 3 次b 出现 2 次3 2失衡。拿两个 a 分别和两个 b 抵消最后剩下一个 a答案是 1正好等于 2 * 3 - 5 1。你可以验证不管操作顺序怎么变最终都不可能比 1 更小。2.2 均衡情况没有绝对多数时能消到只剩 0 或 1反过来如果没有任何一个字符出现次数超过总数的一半也就是 mx n - mx情况就温和很多。理论上你是可以把字符全部消掉或者只剩一个的。为什么因为每次操作移除两个字符所以最终剩余长度的奇偶性一定和原始长度 n 一致。如果 n 是偶数最后可以剩 0 个如果 n 是奇数最后可以剩 1 个。换句话说答案是 n % 2。这里有个细节值得说明不是说随便按什么顺序操作都能达到这个最优结果。比如 s aaabbc总长 6a 出现 3 次b 出现 2 次c 出现 1 次没有绝对多数理论上答案是 0。你可以这样消第一次拿 a 和 c 抵消剩余 a 2 个、b 2 个第二次拿 a 和 b 抵消剩余 a 1 个、b 1 个第三次拿 a 和 b 抵消全部消光。但如果你第一步拿 b 和 c 抵消剩余 a 3 个、b 1 个这时候 a 变成绝对多数了最后只能剩 2 个 a反而变差。所以均衡情况下的结论是“存在一种最优消法能消到 0 或 1”而不是“随便消都能”。构造最优消法的策略也很简单每次选当前数量最多的两个不同字符进行抵消。这个策略能防止某个字符在某一步突然变成绝对多数从而保证整个过程始终处在一个“还能继续消”的状态。2.3 一个公式合并两种情况max(n % 2, 2 * mx - n)既然失衡情况下答案是 2 * mx - n均衡情况下答案是 n % 2那能不能用一个表达式统一能就是ans max(n % 2, 2 * mx - n)这个公式第一次看可能觉得奇怪但拆开看就很自然。失衡时2 * mx - n 是正数而且由于 2 * mx 是偶数2 * mx - n 和 n 同奇偶所以它一定不小于 n % 2max 会取到它。均衡时mx n / 2意味着 2 * mx - n 0max 自然落到 n % 2 上。两种情况被一个 max 完美覆盖。我整理了几个典型样例方便你对照验证输入示例nmx2 * mx - nn % 2最终答案a11111ab21000abc31-111aaabb53111aaaaabbbb95111aaaa44404aabbcc62-200每行都可以手推一下推完这个表格公式基本就刻在脑子里了。3. 代码落地十几行搞定并避开三类边界3.1 Python 实现最简写法公式确定之后代码短得有点不像周赛第二题。Python 可以这样写def minimumLength(s: str) - int: n len(s) cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 mx max(cnt) return max(n % 2, 2 * mx - n)如果题目不保证只有小写字母比如可能包含大写字母或任意 ASCII 字符那就用字典def minimumLengthAnyChar(s: str) - int: n len(s) cnt {} for ch in s: cnt[ch] cnt.get(ch, 0) 1 mx max(cnt.values()) return max(n % 2, 2 * mx - n)这里有个小细节固定数组版本里max(cnt) 会把字符集里不存在的字符也算进来但它们的值是 0而 2 * 0 - n 是负数不可能被 max(n % 2, ...) 选中所以不影响结果。这个写法是安全的不需要额外排除 0。3.2 C 和 Java 的注意点C 版本int minimumLength(string s) { int n s.size(); vectorint cnt(26, 0); for (char c : s) cnt[c - a]; int mx *max_element(cnt.begin(), cnt.end()); return max(n % 2, 2 * mx - n); }Java 版本public int minimumLength(String s) { int n s.length(); int[] cnt new int[26]; for (char c : s.toCharArray()) cnt[c - a]; int mx 0; for (int v : cnt) mx Math.max(mx, v); return Math.max(n % 2, 2 * mx - n); }C 里注意2 * mx - n都是 int 类型正常字符串长度下不会溢出。但如果哪天真遇到长度接近 10^9 的极端数据记得把变量换成 long long避免 2 * mx 这一下直接炸掉 int。3.3 三个边界条件写代码前先想清楚第一个边界是空串和单字符串。空串返回 0单字符返回 1这是公式自然算出来的不用特判。第二个边界是所有字符都相同的情况。比如 s aaaan 4mx 4答案是 4。很多人在这一步会怀疑不是能抵消吗为什么不能消因为操作要求两个不同字符全是同一个字符时找不到合法操作一个都消不掉答案就是原始长度。第三个边界是 n 为奇数且所有字符都只出现一次的情况。比如 s abcden 5mx 1答案应该是 1。这里特别容易错有人会把公式记成 max(0, 2 * mx - n)那结果就是 0。但 0 是不可能的因为每次消两个字符奇数长度的字符串怎么可能最终变成空串所以 n % 2 这一项一定不能丢。4. 周赛复盘三个高频提交错误和自测套路4.1 错误一把“不同字符抵消”理解成“相同字符抵消”字符串最小化类题目里确实有一类操作是“删除两个相同字符”结论完全不同。如果这道题按相同字符抵消去做会得到“统计每个字符出现次数奇偶”的错误解法。有些样例甚至会碰巧对上比如 s aaabb正确答案是 1奇数频次字符统计出来也是 1单看这一个用例根本发现不了问题。但换一个用例就露馅了s aaaaabbbb正确答案是 2而按相同字符抵消算出来是 1。所以拿到题目第一件事一定是反复确认“等量移除”到底约束的是两个字符不同还是相同。我建议读题时把条件圈出来别靠印象做题。4.2 错误二公式少了奇偶性那一项这次周赛提交区里最常见的错误就是把公式写成 max(0, 2 * mx - n)。这个写法在失衡样例上没问题但一到均衡且 n 为奇数的样例就挂。s abcn 3mx 1max(0, -1) 0而真实答案是 1。我自己早期的习惯是推导完公式后立刻把所有长度为 1、2、3 的小样例在脑子里过一遍特别是那种“每种字符各出现一次”的样例。这类样例能同时验证奇偶性和公式结构基本不会放过这类低级错误。4.3 错误三模拟实现太粗糙导致超时也有不少参赛者想到了“每次取最大频次和次大频次抵消”的贪心但实现时每次重新扫哈希表、或者对频次排序复杂度就不合格。正确实现至少需要堆或者有序结构来维护频次每次取前两大复杂度 O(n log n)。这么写虽然能过但这道题既然有 O(n) 的公式解就没必要绕。我的经验是如果一道题只问最终长度并且你发现自己在用数据结构模拟过程先停下来想想有没有数学结论。4.4 用暴力对拍验证公式心里更有底复盘时我写了一个暴力枚举去验证公式。字符串长度很小的时候可以把所有可能的删除顺序都试一遍取最小的剩余长度然后和公式结果做对比。我用随机生成的长度不超过 10 的字符串跑了上千组全部一致之后才完全放心。这种“公式 暴力对拍”的组合拳对字符串最小化这类题非常实用。暴力代码也很短from functools import lru_cache def brute(s): lru_cache(None) def dfs(t): n len(t) ans n for i in range(n): for j in range(i 1, n): if t[i] ! t[j]: nxt t[:i] t[i1:j] t[j1:] ans min(ans, dfs(nxt)) return ans return dfs(s)注意暴力只能用于长度很小的字符串超过 12 个字符枚举量就会爆炸但对拍足够用了。5. 同类模型的扩展看到字符串最小化题先想自由度5.1 变体 A每次删除两个相同字符如果操作改成删除两个相同字符答案等于所有出现次数为奇数的字符数量。因为每个字符之间是独立的出现偶数次的字符可以全部配对被删掉出现奇数次的字符最终必然剩一个。这个结论和本题的“不同字符抵消”很不一样但容易混淆。做题时如果没看清很可能在第一题用错误公式到第二题又用错误公式连错两题。5.2 变体 B每次删除两个相邻且不同的字符如果操作加上“相邻”的限制问题就变了味道。这时位置信息重新变得重要不能再按多重集处理。标准解法是栈模拟遍历每个字符如果栈非空且栈顶字符和当前字符不同就弹栈抵消否则入栈。最后栈剩下的长度就是答案。这类题强调的是动态归约和本题的静态频次统计是两套完全不同的思路。5.3 变体 C每次只能删除首尾且相同的字符还有一种常见变体是只能删除字符串两端且相同的字符问最短能剩多长。这个模型又是另一个方向要从两端向中间收缩每次比较两个端点字符相同就继续删不同就停止。统计频次在这里完全没用核心是端点匹配关系。所以我把这类题的判断顺序固定成三步操作能选任意位置吗删除的两个字符之间有相同或不同的约束吗题目问的是最终长度还是剩余串本身想清楚这三个问题再决定用数学公式、栈还是双指针。5.4 我现在的做题习惯经历了这次周赛之后我给自己定了一个规矩遇到字符串最小化问题先手推小样例再决定算法方向而不是上来就写代码。先拿长度为 3 到 6 的简单字符串试比如 abc、aabb、aaabb、abcabc看答案分别是多少心里对结论有个预期再动手推公式或者设计数据结构。这个习惯帮我避免了很多次“对着错误的模型写出一整段无法通过的代码”的尴尬。最后再分享一个小技巧。对拍验证时不要只生成随机字符串还要专门生成一些极端数据比如全相同字符的串、所有字符频次都相等的串、以及只有一个字符和其余字符频次差 1 的串。这些极端数据最容易暴露公式的边界问题。我自己在验证这道题时就是靠 aaaaabbbb 这种临界用例发现了一个隐藏的奇偶性误区。如果你也想在周赛里少踩坑不妨把这套验证流程用到下一次遇到的最小化问题上。
上周末这场周赛Q2 的 3746 题叫“等量移除后的字符串最小长度”名字听着绕其实核心就一句话给你一个字符串每次操作移除两个不同字符问最终字符串最短能剩多长。这题我一开始想复杂了把它当成字符串模拟题又是双端队列又是指针结果越绕越远。停下手写了几组例子之后才反应过来这题和字符本身没什么关系只和每种字符出现的次数有关。这篇复盘我会把从读题到提交通过的完整思考过程写下来包括公式推导、代码实现、以及我在周赛里踩过的三个坑适合所有在字符串最小化类题目上容易想复杂的朋友。1. 先想清楚等量移除到底在考什么1.1 把操作翻译成“不同颜色球的抵消”题目里说的“等量移除”放到这道题的场景里最常见的理解就是每次同时拿走两个字符而且这两个字符不能相同。我在读题时第一时间把这个操作翻译成了“不同颜色球的抵消”假设字符串里每个字符是一种颜色的球黑色代表 a白色代表 b红色代表 c。操作就是每次从这堆球里挑两个颜色不同的球扔掉最后问这堆球最少还能剩几个。这个翻译看起来简单但它直接决定了整个问题的建模方向。字符串本身是有顺序的可是题目从头到尾没有说只能删除相邻字符也没有说只能删除首尾字符等于每一次操作你都可以随便挑两个位置。这种自由度意味着字符在原始字符串里的位置信息是完全没有用的你根本不需要维护“剩余串长什么样”只需要知道每种字符还剩多少个。本质上这是一个多重集合问题不是一个序列问题。我举个例子s aabbcc 和 s abcabc它们的位置分布完全不一样但作为多重集合是一样的都是每种字符出现两次那么它们能做到的最终结果也完全一样都是消到空。很多选手卡在这一步就是因为脑子里还残留着“字符串必须按顺序处理”的惯性。1.2 直接模拟为什么容易翻车比赛时我最初的想法是维护一个频次哈希表每次取出现次数最多的两个不同字符各减一直到剩不下两个不同字符为止。这个思路本身不是错的但是如果真用数组加循环来找最大值每操作一次都要扫一遍所有字符最坏情况下字符串长度到 10^5操作次数接近 n/2复杂度直接变成 O(n^2)肯定会超时。更别提有人会想用队列维护剩余串、模拟删除后还要拼接那复杂度更难看。周赛里 Q2 这类题目最大的陷阱就是你一旦走进“模拟删除过程”的胡同就很难出来。而实际上如果题目只要求输出长度不要求输出最终的字符串大多数情况下都存在一个绕过模拟的数学结论。这个结论不需要你真正执行操作只需要统计频次、算一个式子。1.3 状态压缩只关心出现次数把所有字符的数量压缩成一个频次数组之后问题就变成一个纯组合问题。假设字符串总长度是 n出现次数最多的那个字符的频次是 mx那么其他所有字符的总数是 n - mx。接下来你只需要回答一个问题当“最大频次的字符”和“其余所有字符”数量失衡时会发生什么均衡时又会发生什么。这两个分支就是整道题的解题钥匙。下面一节我会把两种情况分别推一遍最后合并成一个公式。2. 最小长度公式从哪来失衡与均衡的两种结局2.1 失衡情况一个字符占了半壁江山如果某一个字符的出现次数超过总数的一半也就是 2 * mx n情况就很特殊。假设这个字符是 c。除了 c 之外的所有字符总数是 n - mx比 c 本身还要少。每次操作如果想让剩下的长度尽量小最有效的做法是拿一个 c 和一个非 c 字符抵消。非 c 字符最多只有 n - mx 个所以最多只能进行 n - mx 次这样的抵消。抵消完之后c 还剩mx - (n - mx) 2 * mx - n这些剩下的字符全是 c再也找不到第二个不同字符和它配对操作就停止了。所以失衡情况下的答案是 2 * mx - n。举个例子s aaabb总长 5a 出现 3 次b 出现 2 次3 2失衡。拿两个 a 分别和两个 b 抵消最后剩下一个 a答案是 1正好等于 2 * 3 - 5 1。你可以验证不管操作顺序怎么变最终都不可能比 1 更小。2.2 均衡情况没有绝对多数时能消到只剩 0 或 1反过来如果没有任何一个字符出现次数超过总数的一半也就是 mx n - mx情况就温和很多。理论上你是可以把字符全部消掉或者只剩一个的。为什么因为每次操作移除两个字符所以最终剩余长度的奇偶性一定和原始长度 n 一致。如果 n 是偶数最后可以剩 0 个如果 n 是奇数最后可以剩 1 个。换句话说答案是 n % 2。这里有个细节值得说明不是说随便按什么顺序操作都能达到这个最优结果。比如 s aaabbc总长 6a 出现 3 次b 出现 2 次c 出现 1 次没有绝对多数理论上答案是 0。你可以这样消第一次拿 a 和 c 抵消剩余 a 2 个、b 2 个第二次拿 a 和 b 抵消剩余 a 1 个、b 1 个第三次拿 a 和 b 抵消全部消光。但如果你第一步拿 b 和 c 抵消剩余 a 3 个、b 1 个这时候 a 变成绝对多数了最后只能剩 2 个 a反而变差。所以均衡情况下的结论是“存在一种最优消法能消到 0 或 1”而不是“随便消都能”。构造最优消法的策略也很简单每次选当前数量最多的两个不同字符进行抵消。这个策略能防止某个字符在某一步突然变成绝对多数从而保证整个过程始终处在一个“还能继续消”的状态。2.3 一个公式合并两种情况max(n % 2, 2 * mx - n)既然失衡情况下答案是 2 * mx - n均衡情况下答案是 n % 2那能不能用一个表达式统一能就是ans max(n % 2, 2 * mx - n)这个公式第一次看可能觉得奇怪但拆开看就很自然。失衡时2 * mx - n 是正数而且由于 2 * mx 是偶数2 * mx - n 和 n 同奇偶所以它一定不小于 n % 2max 会取到它。均衡时mx n / 2意味着 2 * mx - n 0max 自然落到 n % 2 上。两种情况被一个 max 完美覆盖。我整理了几个典型样例方便你对照验证输入示例nmx2 * mx - nn % 2最终答案a11111ab21000abc31-111aaabb53111aaaaabbbb95111aaaa44404aabbcc62-200每行都可以手推一下推完这个表格公式基本就刻在脑子里了。3. 代码落地十几行搞定并避开三类边界3.1 Python 实现最简写法公式确定之后代码短得有点不像周赛第二题。Python 可以这样写def minimumLength(s: str) - int: n len(s) cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 mx max(cnt) return max(n % 2, 2 * mx - n)如果题目不保证只有小写字母比如可能包含大写字母或任意 ASCII 字符那就用字典def minimumLengthAnyChar(s: str) - int: n len(s) cnt {} for ch in s: cnt[ch] cnt.get(ch, 0) 1 mx max(cnt.values()) return max(n % 2, 2 * mx - n)这里有个小细节固定数组版本里max(cnt) 会把字符集里不存在的字符也算进来但它们的值是 0而 2 * 0 - n 是负数不可能被 max(n % 2, ...) 选中所以不影响结果。这个写法是安全的不需要额外排除 0。3.2 C 和 Java 的注意点C 版本int minimumLength(string s) { int n s.size(); vectorint cnt(26, 0); for (char c : s) cnt[c - a]; int mx *max_element(cnt.begin(), cnt.end()); return max(n % 2, 2 * mx - n); }Java 版本public int minimumLength(String s) { int n s.length(); int[] cnt new int[26]; for (char c : s.toCharArray()) cnt[c - a]; int mx 0; for (int v : cnt) mx Math.max(mx, v); return Math.max(n % 2, 2 * mx - n); }C 里注意2 * mx - n都是 int 类型正常字符串长度下不会溢出。但如果哪天真遇到长度接近 10^9 的极端数据记得把变量换成 long long避免 2 * mx 这一下直接炸掉 int。3.3 三个边界条件写代码前先想清楚第一个边界是空串和单字符串。空串返回 0单字符返回 1这是公式自然算出来的不用特判。第二个边界是所有字符都相同的情况。比如 s aaaan 4mx 4答案是 4。很多人在这一步会怀疑不是能抵消吗为什么不能消因为操作要求两个不同字符全是同一个字符时找不到合法操作一个都消不掉答案就是原始长度。第三个边界是 n 为奇数且所有字符都只出现一次的情况。比如 s abcden 5mx 1答案应该是 1。这里特别容易错有人会把公式记成 max(0, 2 * mx - n)那结果就是 0。但 0 是不可能的因为每次消两个字符奇数长度的字符串怎么可能最终变成空串所以 n % 2 这一项一定不能丢。4. 周赛复盘三个高频提交错误和自测套路4.1 错误一把“不同字符抵消”理解成“相同字符抵消”字符串最小化类题目里确实有一类操作是“删除两个相同字符”结论完全不同。如果这道题按相同字符抵消去做会得到“统计每个字符出现次数奇偶”的错误解法。有些样例甚至会碰巧对上比如 s aaabb正确答案是 1奇数频次字符统计出来也是 1单看这一个用例根本发现不了问题。但换一个用例就露馅了s aaaaabbbb正确答案是 2而按相同字符抵消算出来是 1。所以拿到题目第一件事一定是反复确认“等量移除”到底约束的是两个字符不同还是相同。我建议读题时把条件圈出来别靠印象做题。4.2 错误二公式少了奇偶性那一项这次周赛提交区里最常见的错误就是把公式写成 max(0, 2 * mx - n)。这个写法在失衡样例上没问题但一到均衡且 n 为奇数的样例就挂。s abcn 3mx 1max(0, -1) 0而真实答案是 1。我自己早期的习惯是推导完公式后立刻把所有长度为 1、2、3 的小样例在脑子里过一遍特别是那种“每种字符各出现一次”的样例。这类样例能同时验证奇偶性和公式结构基本不会放过这类低级错误。4.3 错误三模拟实现太粗糙导致超时也有不少参赛者想到了“每次取最大频次和次大频次抵消”的贪心但实现时每次重新扫哈希表、或者对频次排序复杂度就不合格。正确实现至少需要堆或者有序结构来维护频次每次取前两大复杂度 O(n log n)。这么写虽然能过但这道题既然有 O(n) 的公式解就没必要绕。我的经验是如果一道题只问最终长度并且你发现自己在用数据结构模拟过程先停下来想想有没有数学结论。4.4 用暴力对拍验证公式心里更有底复盘时我写了一个暴力枚举去验证公式。字符串长度很小的时候可以把所有可能的删除顺序都试一遍取最小的剩余长度然后和公式结果做对比。我用随机生成的长度不超过 10 的字符串跑了上千组全部一致之后才完全放心。这种“公式 暴力对拍”的组合拳对字符串最小化这类题非常实用。暴力代码也很短from functools import lru_cache def brute(s): lru_cache(None) def dfs(t): n len(t) ans n for i in range(n): for j in range(i 1, n): if t[i] ! t[j]: nxt t[:i] t[i1:j] t[j1:] ans min(ans, dfs(nxt)) return ans return dfs(s)注意暴力只能用于长度很小的字符串超过 12 个字符枚举量就会爆炸但对拍足够用了。5. 同类模型的扩展看到字符串最小化题先想自由度5.1 变体 A每次删除两个相同字符如果操作改成删除两个相同字符答案等于所有出现次数为奇数的字符数量。因为每个字符之间是独立的出现偶数次的字符可以全部配对被删掉出现奇数次的字符最终必然剩一个。这个结论和本题的“不同字符抵消”很不一样但容易混淆。做题时如果没看清很可能在第一题用错误公式到第二题又用错误公式连错两题。5.2 变体 B每次删除两个相邻且不同的字符如果操作加上“相邻”的限制问题就变了味道。这时位置信息重新变得重要不能再按多重集处理。标准解法是栈模拟遍历每个字符如果栈非空且栈顶字符和当前字符不同就弹栈抵消否则入栈。最后栈剩下的长度就是答案。这类题强调的是动态归约和本题的静态频次统计是两套完全不同的思路。5.3 变体 C每次只能删除首尾且相同的字符还有一种常见变体是只能删除字符串两端且相同的字符问最短能剩多长。这个模型又是另一个方向要从两端向中间收缩每次比较两个端点字符相同就继续删不同就停止。统计频次在这里完全没用核心是端点匹配关系。所以我把这类题的判断顺序固定成三步操作能选任意位置吗删除的两个字符之间有相同或不同的约束吗题目问的是最终长度还是剩余串本身想清楚这三个问题再决定用数学公式、栈还是双指针。5.4 我现在的做题习惯经历了这次周赛之后我给自己定了一个规矩遇到字符串最小化问题先手推小样例再决定算法方向而不是上来就写代码。先拿长度为 3 到 6 的简单字符串试比如 abc、aabb、aaabb、abcabc看答案分别是多少心里对结论有个预期再动手推公式或者设计数据结构。这个习惯帮我避免了很多次“对着错误的模型写出一整段无法通过的代码”的尴尬。最后再分享一个小技巧。对拍验证时不要只生成随机字符串还要专门生成一些极端数据比如全相同字符的串、所有字符频次都相等的串、以及只有一个字符和其余字符频次差 1 的串。这些极端数据最容易暴露公式的边界问题。我自己在验证这道题时就是靠 aaaaabbbb 这种临界用例发现了一个隐藏的奇偶性误区。如果你也想在周赛里少踩坑不妨把这套验证流程用到下一次遇到的最小化问题上。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
