题目描述
思路解析
一句话答案：LeetCode 2981 找出至少出现三次的最长特殊子串用二分答案：长度越大越难凑够三次这条单调性，让判定把串切成一段段同字符再累计验证、往长收缩，时间 O(n log n)、空间 O(1)。
特殊子串、出现三次、可重叠——这题到底在数什么
给一个只含小写字母的串 s。特殊子串指整段只由同一个字符组成，像 aa、ddd 都算；子串是连续非空的一截，可重叠着数。要求出现次数达到三次及以上的最长特殊子串有多长，凑不够就返回负一。题面 s = aaaa 时，长度 2 的 aa 靠重叠出现了三次，答案是 2；s = abcdef 每个字母只出现一次，返回负一。
逐个长度、逐个位置地数，规模压不住
枚举所有子串就有 O(n²) 个：长度从 1 到 n、起点也有 n 个，每个还要判断是不是整段同字符、再数它出现几次，规模一大直接拖垮。二分答案把要试的长度从 n 个压到 O(log n) 个，每轮只扫一遍串统计，量级差出一大截。
长度轴一刀切成两半，才轮到二分登场
把候选长度排成一条轴看：长度 x 能凑够三次，那要求缩到 x−1 更容易——短窗口在同一段能停的位置更多；反过来 x 凑不够，更长的更没戏。于是长度轴被切成两半：短的都可行、长的都不行，答案就是可行那截的右端。与其一个个长度试，不如二分猜长度、拿判定卡一刀再收，这就是二分答案。
判定一个长度行不行，怎么按极长段来数
判定函数 check(x) 很直白：给它一个长度，回答能不能凑够三次。先把 s 切成极长段——连续同字符、左右再扩不出去的片段。一段长度 L 的段里能装几个长度 x 的特殊子串？宽 x 的窗口从左滑到右，能停 max(0, L − x + 1) 个位置，段比 x 短就归零。同一字符可能散在好几段，把位置数全加起来，某个字符累计到 3 长度 x 就可行——这三次不必挤在同一段。取中点 mid = (l + r + 1) // 2 偏上：check(mid) 为真把 l 抬到 mid，为假把 r 收到 mid − 1。
题面 aaaa 走一遍二分，l 和 r 最后停在 2
s = aaaa，n = 4，整串一段 a、长 4。l = 0、r = 4。第一轮 mid = (0 + 4 + 1) // 2 = 2，check(2) 这段贡献 max(0, 4 − 2 + 1) = 3 个 aa，a 累计到 3，长度 2 可行，l 抬到 2。第二轮 l = 2、r = 4，mid = 3，check(3) 只贡献 max(0, 4 − 3 + 1) = 2 个，不到 3，r 收到 2。此时 l = r = 2，循环停，l 不为 0，返回 2。换成 s = abcdef 六段各长 1，长度 1 凑不满三次，l 收到 0，返回负一。
中点取偏下，剩两格时就在原地打转
二分 O(log n) 轮，每轮 check 扫一遍串是 O(n)，合起来 O(n log n)；空间是长度 26 的计数，O(1)。三处只要错一处，整段二分就白跑：中点配 l = mid 必须取偏上 (l + r + 1) // 2，写成偏下时剩相邻两格 mid 恒等于 l、原地不动出不来；算贡献一定要套 max(0, L − x + 1)，段比 x 短时括号里是负数，不归零会扣掉别处段的正确计数、答案偏小甚至变负；最后 l 停在 0 得返回负一，那是连单字符都没出现三次，返回 0 错了。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这条主线:先切极长段,再二分答案长度 x。判可行只看一件事,某个字符把它所有段能提供的长度 x 特殊子串数目加起来,够不够 3 个。下面先把 s 切成段,再动手二分。
先看输入 s · 一排字符：这是输入 s,一共八个字符,下标从 0 到 7。第一步不急着数,先把它切成极长段。所谓极长段,就是一段连续、字符都相同、而且左右再也扩不出去的片段。你顺着看过去:开头单独一个 a,接着单独一个 b,然后连着三个 a,再一个 b,最后两个 a。下面逐段点出来。
第 1 段 · 字符 a · 长度 1：绿色框住的是第 1 段,字符是 a,从下标 0 到 0,长度 1。把它记进段列表,继续往后切。
第 2 段 · 字符 b · 长度 1：绿色框住的是第 2 段,字符是 b,从下标 1 到 1,长度 1。把它记进段列表,继续往后切。
第 3 段 · 字符 a · 长度 3：绿色框住的是第 3 段,字符是 a,从下标 2 到 4,长度 3。这是最长的一段,三个 a 连在一起,后面数长度 2、长度 3 的特殊子串,主要靠它出力。
第 4 段 · 字符 b · 长度 1：绿色框住的是第 4 段,字符是 b,从下标 5 到 5,长度 1。把它记进段列表,继续往后切。
第 5 段 · 字符 a · 长度 2：绿色框住的是第 5 段,字符是 a,从下标 6 到 7,长度 2。切到这里,五段全部出来了:a 长 1、b 长 1、a 长 3、b 长 1、a 长 2。注意字符 a 分散在三段里,后面要把它们的贡献合起来算。
关键公式 · 一段能切出几个长度 x 的特殊子串：先把最关键的一步公式讲透。绿色这段是 aaa,长度 L 等于 3。想在里面找长度 x 等于 2 的 aa,就像拿一个宽度 2 的窗口从左往右滑:能停的位置有 3 减 2 加 1 等于 2 个,分别盖住前两个 a 和后两个 a。一般地,长度 L 的段能切出 max(0, L − x + 1) 个长度 x 的特殊子串;当 x 比 L 还大时这个值会变成负数,用 max 跟 0 一比就归零,表示放不下。这个数目,就是这一段给这个字符贡献的特殊子串次数。
二分登场 · 在长度轴上找最大可行 x：换一张图。这一排数字是候选答案长度 x 的所有取值,从 0 一直到 8。既然 x 越大越难凑够三次、可行性单调,我们就在这条轴上二分。左指针 l 是目前还没否掉的下界,右指针 r 是上界,灰掉的格子是已经排除的长度。开始时范围是从 0 到 8。
取中点 · 先测 x = 4：范围 [0, 8] 取中点偏上,mid 等于 4。为什么偏上,因为下界会写成 l 等于 mid,取偏下会卡在原地死循环,后面坑里细说。现在先问:长度 4 的特殊子串,能不能有某个字符凑够三次。
check(4) · 最长段也放不下长度 4：回到字符串。要放长度 4 的特殊子串,得有一段极长段长度至少是 4。可我们最长的一段就是绿色这个 aaa,才 3 格,连一个长度 4 的都摆不下,贡献是 max(0, 3 − 4 + 1) 等于 0。其余的段更短,贡献全是 0。侧栏 cnt 里 a 和 b 都是 0,没有任何字符到 3。所以 x 等于 4 不可行。
x = 4 不可行 · 上界收到 3：既然 4 不行,那么 4 以及比 4 更长的都不可能了,右边一片灰掉。上界收到 mid 减 1 等于 3,搜索范围变成 [0, 3],接着在里面找。
取中点 · 测 x = 2：在 [0, 3] 里再取中点偏上,mid 等于 2。这一回问:长度 2 的特殊子串,也就是某个字母连着两个,能不能凑够三次。这是关键一测,盯住侧栏 cnt 的变化。
check(2) · aaa 段贡献 2 个 aa：开始给字符 a 数长度 2 的 aa。前面单独的 a 段只有 1 格,放不下 aa,贡献 0,先跳过。走到绿色这段 aaa,长度 3,能放 3 − 2 + 1 等于 2 个 aa。cnt 里 a 记成 2,已经很接近 3 了,就差 1 个。继续往后看还有没有 a 段。
check(2) · aa 段再贡献 1,凑够 3：继续走到最后这段 aa,长度 2,能放 2 − 2 + 1 等于 1 个 aa。把它加到前面的 2 上,cnt 里 a 变成 3,正好达到三次。注意这三个 aa 来自两段不同的极长段,蓝色那段 aaa 出了 2 个,绿色这段 aa 出了 1 个,合起来才够。一旦有字符到 3,判定立刻返回可行,x 等于 2 成立。
x = 2 可行 · 下界抬到 2：2 可行,说明答案至少是 2,先把它记成当前最优,绿色标在长度 2 上。但也许还能更长,所以不是收工,而是把下界 l 抬到 mid 等于 2,继续在 [2, 3] 里往更长的方向试。
取中点 · 测 x = 3：在 [2, 3] 里取中点偏上,mid 等于 3。问长度 3 的特殊子串,也就是某字母连着三个 aaa,能不能凑够三次。绿色的 2 是我们已经拿到手的最优,这次是看能不能突破到 3。
check(3) · aaa 段只贡献 1 个 aaa：给字符 a 数长度 3 的 aaa。绿色这段 aaa 长度 3,恰好只能放 3 − 3 + 1 等于 1 个,就是它自己。cnt 里 a 记成 1,离 3 还差得远。指望后面的 a 段接力,可它们更短。
check(3) · aa 段放不下 aaa,停在 1：走到最后这段 aa,长度只有 2,连一个长度 3 的 aaa 都放不进去,贡献 max(0, 2 − 3 + 1) 等于 0。字符 a 的累计停在 1,b 更是从头到尾都是 0。没有任何字符能把长度 3 的特殊子串凑够三次,所以 x 等于 3 不可行。
x = 3 不可行 · 上界收到 2,二分结束：3 不行,那 3 以上就更不用看了,上界收到 mid 减 1 等于 2。这时候左指针和右指针都落在 2 上,区间只剩一个点,二分到此结束。
收束 · 二分停在 l = 2：二分停在下界 l 等于 2。它不是 0,说明确实存在出现三次的特殊子串,最长那个的长度就是 2。如果 l 最后停在 0,那才表示连长度 1 的单字符都凑不够三次,那种情况返回负一。这里答案是 2。
验证 · 长度 2 的 aa 恰好出现 3 次：回过头验一遍。长度 2 的 aa,在 s 里出现在三个位置:下标 [2,3]、[3,4],这两个都在中间那段 aaa 里,靠重叠数出来;还有一个在结尾的 [6,7]。三个凑齐,达到至少三次,答案 2 稳稳成立。而长度 3 的 aaa 全串只出现 1 次,达不到三次,这就是为什么答案卡在 2。
边界想清:单段长 3 答案 1、单段长 5 答案 3、全是单字符则返回负一。
面试重点:极长段贡献累计到 3、二分最大可行 x、进阶可用保留每字符前三长段做到 O(n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maximumLength(self, s: str) -> int: def check(x: int) -> bool: cnt = defaultdict(int) i = 0 while i < n: j = i + 1 while j < n and s[j] == s[i]: j += 1 cnt[s[i]] += max(0, j - i - x + 1) i = j return max(cnt.values()) >= 3 n = len(s) l, r = 0, n while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return -1 if l == 0 else l复杂度
- 时间：O(n log n)，n 是字符串长度。二分的候选长度范围是 0 到 n,循环 O(log n) 轮;每一轮的 check 都要从头扫一遍字符串框极长段,是 O(n)。两者相乘,总时间 O(n log n)
- 空间：O(1)，按峰值算。计数用一个固定长度 26 的数组,或 Python 里至多 26 个键的字典,和输入规模无关,是常数;二分只用 l、r、mid 几个变量。所以额外空间是 O(1)
易错点
面试追问把动画讲成自己的话
追问这题判可行的核心逻辑是什么?
追问除了二分,还有更快的做法吗?
追问复杂度和易错点各是什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
寻找两个正序数组的中位数
LeetCode 4 · 困难 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题