LeetCode 420这道强密码检验器是我见过最会伪装的困难题。光是函数签名public int strongPasswordChecker(String password)就给人一种这不是个计数题吗的错觉真正动手推一遍才发现插入、删除、替换三把刀只要同时放在桌上问题就从字符串处理变成了成本核算。一位朋友把这道题转发给我时说他追着答案问了很多轮越问越糊涂我后来自己关掉所有题解把三条规则拆开重推了一遍才彻底想明白。这题真的配得上标题里那两个字——值得反复追问。先说清楚这题要干什么一个密码必须同时满足三条规则长度在6到20之间、至少包含小写字母大写字母数字三类字符、不能出现三个及以上连续相同字符。你可以对密码做三种操作插入任意一个字符、删除任意一个字符、替换任意一个字符每次操作算一步。要求返回让密码满足全部条件的最少操作次数。很多人的第一反应是这还不简单统计缺什么补什么、有没有三连拆掉不就行了。但问题在于三种操作会互相影响插入一个字符既能补长度又能拆三连替换一个字符既能补类型又能拆三连删除一个字符虽然不能补类型但可以减少后续需要替换的次数。这些联动关系让简单计数全部失效。我下面把整个推导过程完整走一遍从建模到代码再到一些不太容易想通的边界情况。1. 读题先读坑三条规则的隐藏联动关系1.1 直觉做法错在哪最自然的做法是分三步思考先看长度少了还是多了再看缺哪几类字符最后扫描连续相同字符段把长度超过3的段切开。问题恰恰出在分步思考上因为每一步的答案不能简单相加。举个例子密码是aaaaaa长度6刚好合规但只含一类字符且有两个三连段按直觉需要替换2次来拆三连外加补2类字符似乎要4次操作。实际上2次替换就够了把第3个字符换成大写字母把第5个字符换成数字得到类似aaAaa1的结果既不存在三连又同时补齐了大写和数字。这里的核心是一次替换可以同时完成两件事。反过来看短密码密码是aaa长度只有3。直觉会说需要补3个字符到长度6再补2类缺失类型还要拆掉一组三连一共7次。实际上插3个字符就全部搞定把插入的字符塞进连续段中间既把长度补到6又用新字符隔开了原来的aaa还能顺便让新字符包含大写和数字。答案应该是3。这就是第一个坑三种操作不是三本独立账单而是同一笔预算可以重复花三次。1.2 先定义两个关键变量在深入之前先把两个贯穿全题的核心变量定义清楚。第一个是missing代表缺失的字符类型数量。密码必须同时含有小写、大写、数字三类缺几类就记几。注意密码里可能还有其他特殊字符它们不影响这个统计。第二个是重复段的基础干预次数我后面统一叫repeats。扫描所有长度大于等于3的连续相同字符段对每一段长度为k的连续段记下k // 3把所有段的结果加起来就是repeats。为什么是k // 3而不是别的下一节细说。先把这两个变量放在心里你会发现整道题的解法就是在它们之上做文章。2. 核心建模把重复段按长度模3分类钥匙在这里2.1 一段连续相同字符最少需要几次干预假设有一段长度为k的连续相同字符比如aaaaaa。不管是替换还是插入本质都是往这个纯色段里放入一个异色字符用异色字符把同色字符隔开让任意三个连续位置不可能全是同一个字符。最省的做法是每隔两个位置放一个异色字符。k3时在位置2放一个异色字符变成aXa搞定需要1次k4时在位置2放一个异色字符变成aXaa后面只剩两个a搞定需要1次k5时在位置3放一个异色字符变成aaXaa两边各两个a搞定需要1次k6时在位置3和位置6各放一个异色字符变成aaXaaY需要2次。所以一段长度为k的连续字符至少需要k // 3次干预而且这个次数是可达的。插入操作同样适用因为往纯色段里插入一个异色字符也会把段切开效果和替换一个位置等价。于是repeats就是所有连续段的k // 3之和它是拆掉全部三连的必要且充分的开销。这里有个很多人绕不过去的弯为什么k4只需要1次却写4 // 3 1k5也只需要1次却写5 // 3 1而k6就变成6 // 3 2。关键在每隔两个位置三连块的数量是向下取整的地板除法不要理解成向上取整的(k2)/3。2.2 删除不是等价操作长度每减1省下来的替换不一样替换和插入对重复段的效果是一样的每干预一次消掉一个三连块。但删除不同删除一个字符会让连续段的长度减1从而改变这个段需要的干预次数。这里先澄清一个常见误解很多人以为在aaaa中间删掉一个a会把段拆成两段。实际不会因为删除后剩下的a会重新拼在一起字符串里依然是连续的一段a只是长度从4变成3。删除任意一个位置效果都一样因为所有字符相同。所以删除对段的影响可以精确建模为段长减1。段长减1之后k // 3会怎么变取决于k对3取模的余数。这才是本题真正的钥匙。看几个例子。k3时初始需要1次替换删掉1个字符变成2需要0次替换省1次成本是删1个。k6时初始需要2次删1个变成5需要1次也省1次成本还是删1个。k4时初始需要1次删1个变成3仍然需要1次没省要删2个变成2才降到0次成本是删2个。k7时初始需要2次删1个变成6还是2次删2个变成5降到1次同样是删2个才省1。k5时初始需要1次删1个变4需要1次删2个变3需要1次删3个变2才降到0次成本是删3个。这个规律可以整理成一张表。原段长度kk % 3初始所需替换次数省下1次替换所需删除个数3、6、9...0k//3删1个4、7、10...1k//3删2个5、8、11...2k//3删3个也就是说如果密码超长必须删除一些字符删除操作可以顺便降低后续替换的开销但降价的效率不同在余数为0的段里删1个就省1次替换在余数为1的段里要删2个才省1次在余数为2的段里要删3个才省1次。后面处理长度超过20的情况时就是按这个性价比排序来决定先删哪些段。3. 三个长度区间分别处理每段贪心逻辑都不一样3.1 长度小于6三个下界取最大当密码长度小于6时唯一能加操作的手段是插入因为删除会让长度更短替换虽然不改变长度但不能补长度。这里插入是万能选手一个插入字符可以同时做三件事把长度往6推、补一种缺失类型、把一个异色字符塞进重复段拆三连。于是问题变成三个下界的最大值。第一个下界是必须插入的数量至少6 - n个因为最终长度不能低于6。第二个下界是缺失的类型数missing缺几类至少要插入几个能补类型的字符。第三个下界是重复段需要的干预次数repeats因为每个插入字符可以拆掉一个三连块至少要插入repeats个异色字符才够。因为同一个插入可以同时命中多个目标所以答案不是这三个数相加而是取最大值max(6 - n, missing, repeats)。举个例子aaa长度36 - n 3只有小写所以缺大写和数字两类missing 2一段三连的repeats 1结果是3。实际操作是插3个字符其中一个是大写一个是数字且插入位置选在三个a之间比如aAb1aZ长度6类型齐全没有三连。再验证边界a长度16 - n 5missing 2没有重复段所以repeats 0答案是5。插入5个字符到长度6这5个字符里包含大写和数字即可。3.2 长度在6到20之间只有替换可用长度在6到20之间时插入会让长度超上限删除会让长度低于下限唯一能用的操作是替换。替换一次成本1既能补缺失类型也能拆三连块和插入一样可以一箭双雕。所以答案就是max(missing, repeats)。这里解释一下为什么是取最大值而不是求和。如果repeats 2且missing 2答案2。因为两次替换可以分别落在两个三连段的中间位置同时把两个字符换成缺失的类型两件事一次做完。如果repeats 5但missing 1答案5这5次替换中有1次顺便补了类型其余4次只负责拆三连。一个容易翻车的细节是替换位置不能随手选。比如aaaaaa需要2次替换把第3个字符换掉得到aaXaaa末尾还是有aaa三连应该换成位置3和位置5得到aaXa Ya这种间隔分布才能确保没有三连。算法里不需要真的去模拟替换位置因为k // 3的下界已经保证了存在这种间隔放置方案。3.3 长度超过20删除的顺序就是性价比的顺序长度超过20时至少需要删除n - 20次这是刚性成本无论如何都省不掉。删除不会补类型但能降低后续需要的替换次数。于是总答案的框架是固定删除次数 max(missing, 删除之后的repeats)后半段取max(missing, repeats)的理由和6到20区间完全一样因为删除之后剩下的工作还是只能靠替换来同时解决补类型和拆三连。难点在于删除之后的repeats怎么算。根据2.2节的成本表省下1次替换所需删除个数是1、2、3所以优先删余数为0的段再删余数为1的段最后删余数为2的段。这就是经典的性价比贪心。用21个a来验证。原字符串长度21多出1个字符必须删1次。连续段长度2121 % 3 0初始repeats 21 // 3 7。这个段属于余数0类型删1个字符就能把所需替换数从7降到6。最后答案是1 max(2, 6) 7。手动验证一下删掉1个a后剩20个a需要6次替换来拆6组三连这6次替换里挑两次分别换成大写和数字完全可行。再看一个反直觉的例子ABABABABABABABABABABABAB24个交替大小写字母长度超过20且没有任何三连但缺数字missing 1。必须删4个字符删谁都不影响repeats本来就没有重复段所以答案就是4 max(1, 0) 5。这里删除操作纯粹是交罚款换不来任何替换方面的优惠。实际编码时要注意按桶处理删除配额后最终返回的删除次数必须是原始的n - 20而不是处理过程中剩下的delete_left。delete_left只是还没拿去兑换替换优惠的剩余配额兑换不到的删除依然要执行所以固定成本不能丢。4. 完整实现与测试用例把公式落成能跑的代码4.1 Python实现与关键分支说明def strong_password_checker(password: str) - int: n len(password) # 1. 统计缺失的字符类型数量 has_lower has_upper has_digit False for ch in password: if ch.islower(): has_lower True elif ch.isupper(): has_upper True elif ch.isdigit(): has_digit True missing int(not has_lower) int(not has_upper) int(not has_digit) # 2. 扫描连续相同字符段 cnt [0, 0, 0] # 按段长 % 3 分桶 repeats 0 # 所有段需要的替换次数的总和 i 0 while i n: j i while j n and password[j] password[i]: j 1 seg_len j - i if seg_len 3: repeats seg_len // 3 cnt[seg_len % 3] 1 i j # 3. 长度小于 6三个下界取最大值 if n 6: return max(6 - n, missing, repeats) # 4. 长度在 6 到 20 之间只能替换 if n 20: return max(missing, repeats) # 5. 长度大于 20必须删除 delete_total n - 20 delete_left delete_total # 优先处理 %3 0 的段删 1 个换 1 次替换 use min(delete_left, cnt[0]) repeats - use delete_left - use # 再处理 %3 1 的段删 2 个换 1 次替换 use min(delete_left // 2, cnt[1]) repeats - use delete_left - use * 2 # 最后处理 %3 2 的段删 3 个换 1 次替换 use min(delete_left // 3, cnt[2]) repeats - use delete_left - use * 3 return delete_total max(missing, repeats)几个值得停下来看的点。统计missing时特殊字符不影响判断islower、isupper、isdigit分别处理即可。扫描连续段用双指针一次遍历完成不需要额外空间。删除阶段的三段代码容易写错。处理余数1的桶时用的是delete_left // 2意思是手里剩下的删除配额每2个能兑换1次替换优惠兑换之后要把实际消耗掉的删除配额从delete_left中扣掉即use * 2。余数2的桶同理。如果delete_left还剩下1或2个用不完没关系它只是换不到优惠但删除操作本身不会因为这个而取消所以最终答案仍然要加delete_total。4.2 测试用例与易错点输入输出说明6长度0插入6个字符补齐长度和类型a5插入5个字符补到长度6并补上大写和数字aaa3长度不足、缺2类、一个三连插入3个字符全部解决aaaaaa2长度合法替换2次同时补类型和拆三连aaaaaaaa28个a两个三连块替换2次aaa1112两段三连各需1次替换其中1次顺便补大写aA1aA1aA10已经满足全部条件21个a组成的串7删1个再加6次替换24个AB交替的串5删4个补长度再替换1次补数字边界条件上最容易踩的坑有三个。第一长度恰好是6或20的时候走哪个分支别弄混。刚好6走n 20的分支刚好20也一样不需要删除。第二只统计长度大于等于3的连续段长度1和2的段完全不需要处理。第三删除阶段的三个桶在实现时不要试图用循环去模拟逐段删除直接用桶的数量和删除配额做乘法级别的计算一次到位。5. 刷题之外的思考这道题在真实业务里到底映射什么5.1 从编辑距离到多约束优化很多密码强度校验需求本质上就是这道题的简化版。真实系统里常见的校验是密码必须包含大写、小写、数字、特殊字符长度至少8位不能出现连续重复字符但几乎不会有系统真去计算最少改多少次才能合规。这道题把编辑距离的三个基本操作插入、删除、替换和多条硬约束揉在一起本质上是个带约束的最小编辑次数问题。这种刚性成本 柔性成本拆解的方式在做系统设计时也很有用。先看哪些操作是不可回避的比如长度超了就必须删再看哪些操作是可以互相抵消的比如替换既能补类型又能拆三连。把问题拆成固定开销和可优化开销比直接硬套动态规划清晰得多。5.2 一个立刻能扩展的变体如果题目把不能出现三个连续相同字符改成不能出现L个连续相同字符这段推导可以平滑迁移。连续段的干预次数从k // 3变成k // L删除省1次替换的成本也按k % L分桶余数0的桶删1个就省1次余数1的桶删2个才省1次依此类推。整道题的代码结构几乎不用变只是把魔法数字3换成L。这也是为什么我强烈建议不要背这道题的代码而是把按模分类的建模方式吃透。模运算在这里不是数学游戏它精准描述了删除字符到达哪个阈值时会让一个段的替换需求刚好下降一档。理解了这一点遇到类似题目你就有章法了。最后分享一个个人体会。我最初手推时在短串区间绕了很久总想用6 - n missing repeats这类加法公式后来拿aaa和空串两个例子一验立刻发现加法会把插入的复用能力重复计算。如果你也在这题上卡住别急着看答案先在纸上把aaa、21个a、24个交替串这三个输入手推一遍推完基本上整个贪心逻辑就长在脑子里了。之后再回来看代码你会发现剩下的只是把思路翻译成语法而已。