单字符重复子串的最大长度 图解题解
这道题到底在问什么
- 输入
- text = "ababa"
- 输出
- 3
- 输入
- text = "aaabaaa"(本节演示)
- 输出
- 6
最优解：一步一步想明白
- 3记牢三步: 数左段 l, 跨一个数右段 r, 候选 = min(l+r+1, 这个字母总数)。下面每一帧都在套它。
- 4上面这排是要演示的字符串 a a a b a a a, 一共 7 个字符。先把每个字母数清楚: a 有 6 个, b 有 1 个, 记在右边面板。接下来按「相同字符连成一段」分组, 一段一段看哪段能换出最长的同字符子串。当前最优答案先记 0。
- 5从第 0 位起开一个新组, 字母是 a。先数它本身这一段有多长, 第 0 位是 a, 左段长度 l 记到 1。
- 6继续往右, 第 1 位还是 a, 左段长度 l 数到 2。
- 7继续往右, 第 2 位还是 a, 左段长度 l 数到 3。
- 8第 3 位变成了 b, 不再是 a, 这一组的左段就停在这里, 左段长度 l = 3。
- 9这一组想更长, 就用唯一的那一次交换, 把中间这个 b(第 3 位, 标红)换出去。换走之后, 看它右边还连着几个 a, 能不能接上来。
- 10越过那个 b 往右看, 第 4 位也是 a, 右段长度 r 数到 1。
- 11越过那个 b 往右看, 第 5 位也是 a, 右段长度 r 数到 2。
- 12越过那个 b 往右看, 第 6 位也是 a, 右段长度 r 数到 3。
- 13右边也数到字符串末尾, 这一组的右段长度 r 定格在 3。
- 14把左段 l = 3 和右段 r = 3 接起来, 中间空出的那一位再换进一个 a, 候选长度 = 3 + 3 + 1 = 7。那个加一, 就是换进来补上中间的那个 a。
- 15可是全场只有 6 个 a, 要换进来的那个 a 必须真实存在。候选 7 超过了总数 6, 所以这一组实际最多排出 6 个 a。6 比原来的最优 0 大, 刷新最优答案 ans = 6。
- 16从第 3 位起开一个新组, 字母是 b。先数它本身这一段有多长, 第 3 位是 b, 左段长度 l 记到 1。
- 17第 4 位变成了 a, 不再是 b, 这一组的左段就停在这里, 左段长度 l = 1。
- 18这一组想更长, 就用唯一的那一次交换, 把中间这个 a(第 4 位, 标红)换出去。换走之后, 看它右边还连着几个 b, 能不能接上来。
- 19第 5 位是 a 了, 不是 b, 右段停在这里, 右段长度 r = 0。
- 20把左段 l = 1 和右段 r = 0 接起来, 中间空出的那一位再换进一个 b, 候选长度 = 1 + 0 + 1 = 2。那个加一, 就是换进来补上中间的那个 b。
- 21可是全场只有 1 个 b, 要换进来的那个 b 必须真实存在。候选 2 超过了总数 1, 所以这一组实际最多排出 1 个 b。1 没超过当前最优 6, ans 保持 6。
- 22从第 4 位起开一个新组, 字母是 a。先数它本身这一段有多长, 第 4 位是 a, 左段长度 l 记到 1。
- 23继续往右, 第 5 位还是 a, 左段长度 l 数到 2。
- 24继续往右, 第 6 位还是 a, 左段长度 l 数到 3。
- 25数到第 6 位就到字符串末尾了, 这一组 a 的左段长度 l 定格在 3。
- 26这一组 a 一直顶到字符串末尾, 右边没有位置可以向右跨, 所以右段 r = 0。但它左边紧挨着一个 b(第 3 位, 已标红): 只要整串里还有多余的 a, 就能用那一次交换把这个 b 换成 a, 把这一组往左接长一个。
- 27这一组顶在字符串末尾, 右边没法向右跨, 右段 r = 0。能加一, 是因为它左边紧挨着一个 b(第 3 位, 标红): 只要整串还有多余的 a, 就能把这个 b 换成 a, 把这组拼到 l + r + 1 = 3 + 0 + 1 = 4 个 a。
- 28a 的总数有 6 个, 够换, 所以这一组实打实能排出 4 个 a。4 没超过当前最优 6, ans 保持 6。
- 29所有组都看完了。最好的是第 0 组那段 a: 左边 3 个、右边 3 个, 中间隔着一个 b。一次交换就是把某个 a 和中间那个 b 对调: b 变成 a 接上两段, 但被对调走的那个 a 让某一端少一个, 所以全串总共只有 6 个 a, 最长就是 6。
⚠️ 容易写错的地方
✗ 错：以为能多换几个位置, 把好几个不同字符都跨过去
✓ 对：只能交换一次, 一段里最多跨过一个不同字符
题目限定一次交换, 跨两个不同字符需要两次, 不允许
✗ 错：直接拿 l + r + 1 当答案, 忘了字母不够的情况
✓ 对：要对 min(l + r + 1, 该字母总数) 封顶
换进中间的那个相同字符必须真实存在, 总数不够就拼不出那么长, 比如 "aaabaaa" 候选 7 但只有 6 个 a
✗ 错：处理完一段后 i 只加 1, 同一段被反复算
✓ 对：处理完一段, i 直接跳到这一段末尾的下一位 j
每段只需以它的起点算一次, i 跳到段末后面才不重复扫描, 保证线性
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(n)
n 是字符串长度。i 每轮直接跳到本段末尾, 右段也只往后多看一小段, 每个位置被看的次数是常数, 整体线性
空间
O(1)
只用一个长度 26 的计数桶(Python 的 Counter 最多 26 个键), 和字符串多长无关, 算常数级
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 单字符重复子串的最大长度 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么候选是 l + r + 1 而不是 l + r?+
因为这一次交换不光是把中间那个不同字符换走, 还能从字符串别处搬一个相同字符填到空出来的中间位置, 左段、补进来的这一个、右段三段连成一片, 所以是 l 加 r 再加 1。但这有个前提: 别处真有多余的相同字符可搬。如果没有, 也就是这个字母的总数正好等于 l 加 r, 那个加 1 就拼不出来, 会被 min 压回 l 加 r。
这题和经典的定长滑动窗口是一回事吗?+
思路相通但更省事。相同字符天然连成一段段, 直接按段扫、每段只看「自己 + 跨一个 + 后面一段」就够了, 不必维护一个变长窗口。也有人用滑窗维护「窗口内除最多字符外其它至多 1 个」来做, 但按相同字符分组写起来更直接、更好读。
时间和空间复杂度是多少?+
时间 O(n), n 是字符串长度。外层 i 每轮直接跳到当前段的末尾下一位, 右段也只多看一小段相同字符, 每个位置被看的次数是常数, 合起来是一遍线性扫描。空间 O(1), 只需要一个长度 26 的计数桶来记每个字母出现多少次, 和字符串多长没关系。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 单字符重复子串的最大长度 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。