单字符重复子串的最大长度 图解题解

换一次字符，要让哪一段变最长

给一个只含小写字母的字符串 text，允许你挑两个位置上的字符互换一次，也允许一次都不换，而换进来的字符必须是串里本来就有的。换完之后，在结果里找一段「全是同一个字符」的子串，问这一段最长能有多长。题面 text="ababa" 时答案是 3，text="aaabaaa" 时答案是 6。

两两枚举交换位置，暴力法要跑三层

串长 n，最直白的做法是枚举「交换哪两个位置」——两两配对就有 n² 种换法，每换一次还得重新扫一遍串、量出最长的同字符段，又是一层 n，三层叠起来是 O(n³)，串一长就跑不动。真正的浪费在于：相同字符本来就一段一段挨着排好，枚举交换却把这层现成的结构整个抹平。

相同字符早就连成段，何必再框一个窗口

既然相同字符天生连成一段段，与其维护一个来回伸缩的窗口，不如直接按段扫。先用一个计数桶记下每个字母在整串里出现多少次（a 有几个、b 有几个），后面判断「够不够换」要用它。然后从左到右把串切成一段段相同字符，对每一段单独问一句：用那唯一的一次交换，它最长能撑到多少。

一段字符怎么算它能撑到多长

站在某一段的起点，先数它自己有多长，记成左段 l。左段会停在第一个不同的字符上，那正是它右边那个「拦路」的字符。这一次交换恰好用来把拦路字符换走，于是跳过它、继续数右边还连着几个相同字符，记成右段 r。左段、换进中间空位的那一个、右段接成一整片，候选长度就是 l + r + 1。那个加一，是从串里别处搬一个相同字符填进中间。但前提是别处真有多余的同字符可搬：如果这个字母的总数还不到 l + r + 1，就拼不出那么长，得让总数把候选压回来，即 min(l + r + 1, 该字母总数)。每段算完，起点直接跳到这一段末尾的下一位，不回头重算。

aaabaaa 逐段数下来，6 就这么冒出来

用 text="aaabaaa" 走一遍，先数清 a 有 6 个、b 有 1 个。第一段从第 0 位起是 a，数到第 3 位撞上 b，左段 l=3；跨过这个 b，右边第 4、5、6 位又接着三个 a，右段 r=3；候选 l+r+1=7，可 a 拢共只有 6 个，min(7, 6)=6，答案先记成 6。第二段是那个 b，左段 l=1，跳过右边的 a 后再没别的 b，右段 r=0，候选 min(1+0+1, 1)=1，够不上 6。第三段又是 a（第 4 到第 6 位），左段 l=3，已经顶到串尾、右边没得跨，右段 r=0，候选 min(3+0+1, 6)=4，仍不敌 6。三段都看完，最长就是 6。

候选 7 却只能拿 6，卡在字母不够

每段起点只被外层走一次、右段也只多看一小段相同字符，整串一遍扫完，时间 O(n)；计数桶最多装 26 个字母，与串多长无关，空间 O(1)。串里全是同一个字符时压根不用换，答案就是串长；全不相同的字符各自成段、别处没有第二个同字符可搬，候选 1+0+1=2 会被总数 1 压回 1。最容易漏的是候选算出 7、a 却只有 6 那种，第 7 个字符凭空变不出来，必须让总数给候选封顶。

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 maxRepOpt1(self, text: str) -> int:
        cnt = Counter(text)
        n = len(text)
        ans = i = 0
        while i < n:
            j = i
            while j < n and text[j] == text[i]:
                j += 1
            l = j - i
            k = j + 1
            while k < n and text[k] == text[i]:
                k += 1
            r = k - j - 1
            ans = max(ans, min(l + r + 1, cnt[text[i]]))
            i = j
        return ans

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 maxRepOpt1(string text) {
        int cnt[26] = {0};
        for (char& c : text) {
            ++cnt[c - 'a'];
        }
        int n = text.size();
        int ans = 0, i = 0;
        while (i < n) {
            int j = i;
            while (j < n && text[j] == text[i]) {
                ++j;
            }
            int l = j - i;
            int k = j + 1;
            while (k < n && text[k] == text[i]) {
                ++k;
            }
            int r = k - j - 1;
            ans = max(ans, min(l + r + 1, cnt[text[i] - 'a']));
            i = j;
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int maxRepOpt1(String text) {
        int[] cnt = new int[26];
        int n = text.length();
        for (int i = 0; i < n; ++i) {
            ++cnt[text.charAt(i) - 'a'];
        }
        int ans = 0, i = 0;
        while (i < n) {
            int j = i;
            while (j < n && text.charAt(j) == text.charAt(i)) {
                ++j;
            }
            int l = j - i;
            int k = j + 1;
            while (k < n && text.charAt(k) == text.charAt(i)) {
                ++k;
            }
            int r = k - j - 1;
            ans = Math.max(ans, Math.min(l + r + 1, cnt[text.charAt(i) - 'a']));
            i = j;
        }
        return ans;
    }
}