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

特殊子串、出现三次、可重叠——这题到底在数什么

给一个只含小写字母的串 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 错了。

Python

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

C++

#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;
    }
};

Java

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;
    }
}