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

这道题到底在问什么

输入

s = "aaaa"

输出

2

输入

s = "abcdef"

输出

负一

输入

s = "abcaba"

输出

1

最优解：一步一步想明白

1. 3记牢这条主线:先切极长段,再二分答案长度 x。判可行只看一件事,某个字符把它所有段能提供的长度 x 特殊子串数目加起来,够不够 3 个。下面先把 s 切成段,再动手二分。
2. 4准备:切极长段这是输入 s,一共八个字符,下标从 0 到 7。第一步不急着数,先把它切成极长段。所谓极长段,就是一段连续、字符都相同、而且左右再也扩不出去的片段。你顺着看过去:开头单独一个 a,接着单独一个 b,然后连着三个 a,再一个 b,最后两个 a。下面逐段点出来。
3. 5切段:第 1 段绿色框住的是第 1 段,字符是 a,从下标 0 到 0,长度 1。把它记进段列表,继续往后切。
4. 6切段:第 2 段绿色框住的是第 2 段,字符是 b,从下标 1 到 1,长度 1。把它记进段列表,继续往后切。
5. 7切段:第 3 段绿色框住的是第 3 段,字符是 a,从下标 2 到 4,长度 3。这是最长的一段,三个 a 连在一起,后面数长度 2、长度 3 的特殊子串,主要靠它出力。
6. 8切段:第 4 段绿色框住的是第 4 段,字符是 b,从下标 5 到 5,长度 1。把它记进段列表,继续往后切。
7. 9切段:第 5 段绿色框住的是第 5 段,字符是 a,从下标 6 到 7,长度 2。切到这里,五段全部出来了:a 长 1、b 长 1、a 长 3、b 长 1、a 长 2。注意字符 a 分散在三段里,后面要把它们的贡献合起来算。
8. 10公式:max(0, L − x + 1)先把最关键的一步公式讲透。绿色这段是 aaa,长度 L 等于 3。想在里面找长度 x 等于 2 的 aa,就像拿一个宽度 2 的窗口从左往右滑:能停的位置有 3 减 2 加 1 等于 2 个,分别盖住前两个 a 和后两个 a。一般地,长度 L 的段能切出 max(0, L − x + 1) 个长度 x 的特殊子串;当 x 比 L 还大时这个值会变成负数,用 max 跟 0 一比就归零,表示放不下。这个数目,就是这一段给这个字符贡献的特殊子串次数。
9. 11二分区间 [0, 8]换一张图。这一排数字是候选答案长度 x 的所有取值,从 0 一直到 8。既然 x 越大越难凑够三次、可行性单调,我们就在这条轴上二分。左指针 l 是目前还没否掉的下界,右指针 r 是上界,灰掉的格子是已经排除的长度。开始时范围是从 0 到 8。
10. 12测 x = 4范围 [0, 8] 取中点偏上,mid 等于 4。为什么偏上,因为下界会写成 l 等于 mid,取偏下会卡在原地死循环,后面坑里细说。现在先问:长度 4 的特殊子串,能不能有某个字符凑够三次。
11. 13x = 4 判定回到字符串。要放长度 4 的特殊子串,得有一段极长段长度至少是 4。可我们最长的一段就是绿色这个 aaa,才 3 格,连一个长度 4 的都摆不下,贡献是 max(0, 3 − 4 + 1) 等于 0。其余的段更短,贡献全是 0。侧栏 cnt 里 a 和 b 都是 0,没有任何字符到 3。所以 x 等于 4 不可行。
12. 14区间 [0, 3]既然 4 不行,那么 4 以及比 4 更长的都不可能了,右边一片灰掉。上界收到 mid 减 1 等于 3,搜索范围变成 [0, 3],接着在里面找。
13. 15测 x = 2在 [0, 3] 里再取中点偏上,mid 等于 2。这一回问:长度 2 的特殊子串,也就是某个字母连着两个,能不能凑够三次。这是关键一测,盯住侧栏 cnt 的变化。
14. 16x = 2 累计中开始给字符 a 数长度 2 的 aa。前面单独的 a 段只有 1 格,放不下 aa,贡献 0,先跳过。走到绿色这段 aaa,长度 3,能放 3 − 2 + 1 等于 2 个 aa。cnt 里 a 记成 2,已经很接近 3 了,就差 1 个。继续往后看还有没有 a 段。
15. 17x = 2 达标继续走到最后这段 aa,长度 2,能放 2 − 2 + 1 等于 1 个 aa。把它加到前面的 2 上,cnt 里 a 变成 3,正好达到三次。注意这三个 aa 来自两段不同的极长段,蓝色那段 aaa 出了 2 个,绿色这段 aa 出了 1 个,合起来才够。一旦有字符到 3,判定立刻返回可行,x 等于 2 成立。
16. 18区间 [2, 3]2 可行,说明答案至少是 2,先把它记成当前最优,绿色标在长度 2 上。但也许还能更长,所以不是收工,而是把下界 l 抬到 mid 等于 2,继续在 [2, 3] 里往更长的方向试。
17. 19测 x = 3在 [2, 3] 里取中点偏上,mid 等于 3。问长度 3 的特殊子串,也就是某字母连着三个 aaa,能不能凑够三次。绿色的 2 是我们已经拿到手的最优,这次是看能不能突破到 3。
18. 20x = 3 累计中给字符 a 数长度 3 的 aaa。绿色这段 aaa 长度 3,恰好只能放 3 − 3 + 1 等于 1 个,就是它自己。cnt 里 a 记成 1,离 3 还差得远。指望后面的 a 段接力,可它们更短。
19. 21x = 3 不达标走到最后这段 aa,长度只有 2,连一个长度 3 的 aaa 都放不进去,贡献 max(0, 2 − 3 + 1) 等于 0。字符 a 的累计停在 1,b 更是从头到尾都是 0。没有任何字符能把长度 3 的特殊子串凑够三次,所以 x 等于 3 不可行。
20. 22区间 [2, 2]3 不行,那 3 以上就更不用看了,上界收到 mid 减 1 等于 2。这时候左指针和右指针都落在 2 上,区间只剩一个点,二分到此结束。
21. 23答案 = 2二分停在下界 l 等于 2。它不是 0,说明确实存在出现三次的特殊子串,最长那个的长度就是 2。如果 l 最后停在 0,那才表示连长度 1 的单字符都凑不够三次,那种情况返回负一。这里答案是 2。
22. 24答案 2 成立回过头验一遍。长度 2 的 aa,在 s 里出现在三个位置:下标 [2,3]、[3,4],这两个都在中间那段 aaa 里,靠重叠数出来;还有一个在结尾的 [6,7]。三个凑齐,达到至少三次,答案 2 稳稳成立。而长度 3 的 aaa 全串只出现 1 次,达不到三次,这就是为什么答案卡在 2。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        int l = 0, r = n;
        auto check = [&](int x) {
            int cnt[26]{};
            for (int i = 0; i < n;) {
                int j = i + 1;
                while (j < n && s[j] == s[i]) {
                    ++j;
                }
                int k = s[i] - 'a';
                cnt[k] += max(0, j - i - x + 1);
                if (cnt[k] >= 3) {
                    return true;
                }
                i = j;
            }
            return false;
        };
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l == 0 ? -1 : l;
    }
};

import java.util.*;
class Solution {
    private String s;
    private int n;

    public int maximumLength(String s) {
        this.s = s;
        n = s.length();
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l == 0 ? -1 : l;
    }

    private boolean check(int x) {
        int[] cnt = new int[26];
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int k = s.charAt(i) - 'a';
            cnt[k] += Math.max(0, j - i - x + 1);
            if (cnt[k] >= 3) {
                return true;
            }
            i = j;
        }
        return false;
    }
}

复杂度

面试官可能追问