找出出现至少三次的最长特殊子字符串 I

记牢这条主线:先切极长段,再二分答案长度 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)。