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"。不管是替换还是插入，本质都是往这个纯色段里放入一个"异色字符"，用异色字符把同色字符隔开，让任意三个连续位置不可能全是同一个字符。

最省的做法是每隔两个位置放一个异色字符。k=3时，在位置2放一个异色字符，变成"aXa"，搞定，需要1次；k=4时，在位置2放一个异色字符，变成"aXaa"，后面只剩两个a，搞定，需要1次；k=5时，在位置3放一个异色字符，变成"aaXaa"，两边各两个a，搞定，需要1次；k=6时，在位置3和位置6各放一个异色字符，变成"aaXaaY"，需要2次。

所以一段长度为k的连续字符，至少需要k // 3次干预，而且这个次数是可达的。插入操作同样适用，因为往纯色段里插入一个异色字符也会把段切开，效果和替换一个位置等价。于是repeats就是所有连续段的k // 3之和，它是"拆掉全部三连"的必要且充分的开销。

这里有个很多人绕不过去的弯：为什么k=4只需要1次却写4 // 3 = 1，k=5也只需要1次却写5 // 3 = 1，而k=6就变成6 // 3 = 2。关键在"每隔两个位置"，三连块的数量是向下取整的地板除法，不要理解成向上取整的(k+2)/3。

2.2 删除不是等价操作：长度每减1，省下来的替换不一样

替换和插入对重复段的效果是一样的，每干预一次消掉一个三连块。但删除不同，删除一个字符会让连续段的长度减1，从而改变这个段需要的干预次数。

这里先澄清一个常见误解：很多人以为在"aaaa"中间删掉一个a，会把段拆成两段。实际不会，因为删除后剩下的a会重新拼在一起，字符串里依然是连续的一段a，只是长度从4变成3。删除任意一个位置效果都一样，因为所有字符相同。所以删除对段的影响可以精确建模为"段长减1"。

段长减1之后，k // 3会怎么变，取决于k对3取模的余数。这才是本题真正的钥匙。

看几个例子。k=3时，初始需要1次替换，删掉1个字符变成2，需要0次替换，省1次，成本是删1个。k=6时，初始需要2次，删1个变成5，需要1次，也省1次，成本还是删1个。k=4时，初始需要1次，删1个变成3，仍然需要1次，没省；要删2个变成2，才降到0次，成本是删2个。k=7时，初始需要2次，删1个变成6还是2次，删2个变成5降到1次，同样是删2个才省1。

k=5时，初始需要1次，删1个变4需要1次，删2个变3需要1次，删3个变2才降到0次，成本是删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"长度3，6 - n = 3，只有小写所以缺大写和数字两类，missing = 2，一段三连的repeats = 1，结果是3。实际操作是插3个字符，其中一个是大写一个是数字，且插入位置选在三个a之间，比如"aAb1aZ"，长度6，类型齐全，没有三连。

再验证边界："a"长度1，6 - n = 5，missing = 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次。连续段长度21，21 % 3 = 0，初始repeats = 21 // 3 = 7。这个段属于余数0类型，删1个字符就能把所需替换数从7降到6。最后答案是1 + max(2, 6) = 7。手动验证一下：删掉1个a后剩20个a，需要6次替换来拆6组三连，这6次替换里挑两次分别换成大写和数字，完全可行。

再看一个反直觉的例子："ABABABABABABABABABABABAB"，24个交替大小写字母，长度超过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或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个交替串这三个输入手推一遍，推完基本上整个贪心逻辑就长在脑子里了。之后再回来看代码，你会发现剩下的只是把思路翻译成语法而已。