题目描述
思路解析动画文字版
记牢三步: 数左段 l, 跨一个数右段 r, 候选 = min(l+r+1, 这个字母总数)。下面每一帧都在套它。
总览 · 先数清每个字母的总数：上面这排是要演示的字符串 a a a b a a a, 一共 7 个字符。先把每个字母数清楚: a 有 6 个, b 有 1 个, 记在右边面板。接下来按「相同字符连成一段」分组, 一段一段看哪段能换出最长的同字符子串。当前最优答案先记 0。
数左段 · a 已连 1 个：从第 0 位起开一个新组, 字母是 a。先数它本身这一段有多长, 第 0 位是 a, 左段长度 l 记到 1。
数左段 · a 已连 2 个：继续往右, 第 1 位还是 a, 左段长度 l 数到 2。
数左段 · a 已连 3 个：继续往右, 第 2 位还是 a, 左段长度 l 数到 3。
左段定格 · l = 3：第 3 位变成了 b, 不再是 a, 这一组的左段就停在这里, 左段长度 l = 3。
跨过一个 b：这一组想更长, 就用唯一的那一次交换, 把中间这个 b(第 3 位, 标红)换出去。换走之后, 看它右边还连着几个 a, 能不能接上来。
数右段 · 又接 1 个 a：越过那个 b 往右看, 第 4 位也是 a, 右段长度 r 数到 1。
数右段 · 又接 2 个 a：越过那个 b 往右看, 第 5 位也是 a, 右段长度 r 数到 2。
数右段 · 又接 3 个 a：越过那个 b 往右看, 第 6 位也是 a, 右段长度 r 数到 3。
右段定格 · r = 3：右边也数到字符串末尾, 这一组的右段长度 r 定格在 3。
候选长度 = 7：把左段 l = 3 和右段 r = 3 接起来, 中间空出的那一位再换进一个 a, 候选长度 = 3 + 3 + 1 = 7。那个加一, 就是换进来补上中间的那个 a。
封顶 · 取 6：可是全场只有 6 个 a, 要换进来的那个 a 必须真实存在。候选 7 超过了总数 6, 所以这一组实际最多排出 6 个 a。6 比原来的最优 0 大, 刷新最优答案 ans = 6。
数左段 · b 已连 1 个：从第 3 位起开一个新组, 字母是 b。先数它本身这一段有多长, 第 3 位是 b, 左段长度 l 记到 1。
左段定格 · l = 1：第 4 位变成了 a, 不再是 b, 这一组的左段就停在这里, 左段长度 l = 1。
跨过一个 a：这一组想更长, 就用唯一的那一次交换, 把中间这个 a(第 4 位, 标红)换出去。换走之后, 看它右边还连着几个 b, 能不能接上来。
右段定格 · r = 0：第 5 位是 a 了, 不是 b, 右段停在这里, 右段长度 r = 0。
候选长度 = 2：把左段 l = 1 和右段 r = 0 接起来, 中间空出的那一位再换进一个 b, 候选长度 = 1 + 0 + 1 = 2。那个加一, 就是换进来补上中间的那个 b。
封顶 · 取 1：可是全场只有 1 个 b, 要换进来的那个 b 必须真实存在。候选 2 超过了总数 1, 所以这一组实际最多排出 1 个 b。1 没超过当前最优 6, ans 保持 6。
数左段 · a 已连 1 个：从第 4 位起开一个新组, 字母是 a。先数它本身这一段有多长, 第 4 位是 a, 左段长度 l 记到 1。
数左段 · a 已连 2 个：继续往右, 第 5 位还是 a, 左段长度 l 数到 2。
数左段 · a 已连 3 个：继续往右, 第 6 位还是 a, 左段长度 l 数到 3。
左段定格 · l = 3：数到第 6 位就到字符串末尾了, 这一组 a 的左段长度 l 定格在 3。
到末尾 · 只能向左借：这一组 a 一直顶到字符串末尾, 右边没有位置可以向右跨, 所以右段 r = 0。但它左边紧挨着一个 b(第 3 位, 已标红): 只要整串里还有多余的 a, 就能用那一次交换把这个 b 换成 a, 把这一组往左接长一个。
候选长度 = 4：这一组顶在字符串末尾, 右边没法向右跨, 右段 r = 0。能加一, 是因为它左边紧挨着一个 b(第 3 位, 标红): 只要整串还有多余的 a, 就能把这个 b 换成 a, 把这组拼到 l + r + 1 = 3 + 0 + 1 = 4 个 a。
封顶 · 取 4：a 的总数有 6 个, 够换, 所以这一组实打实能排出 4 个 a。4 没超过当前最优 6, ans 保持 6。
完成 · 答案 6：所有组都看完了。最好的是第 0 组那段 a: 左边 3 个、右边 3 个, 中间隔着一个 b。一次交换就是把某个 a 和中间那个 b 对调: b 变成 a 接上两段, 但被对调走的那个 a 让某一端少一个, 所以全串总共只有 6 个 a, 最长就是 6。
边界: 全同不用换、全不同最多 1、想接长还得看这个字母总数够不够。
面试重点: 加 1 来自换进一个相同字符(没多余就被封顶)、按相同字符分组比变长滑窗更直接、时间 O(n) 空间 O(1)。
参考代码
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 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复杂度
- 时间：O(n)，n 是字符串长度。i 每轮直接跳到本段末尾, 右段也只往后多看一小段, 每个位置被看的次数是常数, 整体线性
- 空间：O(1)，只用一个长度 26 的计数桶(Python 的 Counter 最多 26 个键), 和字符串多长无关, 算常数级
易错点
面试追问把动画讲成自己的话
追问为什么候选是 l + r + 1 而不是 l + r?
追问这题和经典的定长滑动窗口是一回事吗?
追问时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
大小为 K 且平均值大于等于阈值的子数组数目
LeetCode 1343 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题