LeetCode 题解工作台
单字符重复子串的最大长度
如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。 给你一个字符串 text ，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。 示例 1： 输入： text = "ababa" 输出： 3 示例 2： 输入： text = "aaa…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
我们先用哈希表或数组 统计字符串 中每个字符出现的次数。 接下来，我们定义一个指针 ，初始时 $i = 0$。每一次，我们将指针 指向 ，并不断地向右移动 ，直到 指向的字符与 指向的字符不同，此时我们得到了一个长度为 $l = j - i$ 的子串 ，其中所有字符都相同。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。
示例 1：
输入：text = "ababa" 输出：3
示例 2：
输入：text = "aaabaaa" 输出：6
示例 3：
输入：text = "aaabbaaa" 输出：4
示例 4：
输入：text = "aaaaa" 输出：5
示例 5：
输入：text = "abcdef" 输出：1
提示：
1 <= text.length <= 20000text仅由小写英文字母组成。
解题思路
方法一：双指针
我们先用哈希表或数组 统计字符串 中每个字符出现的次数。
接下来，我们定义一个指针 ，初始时 。每一次，我们将指针 指向 ，并不断地向右移动 ，直到 指向的字符与 指向的字符不同，此时我们得到了一个长度为 的子串 ，其中所有字符都相同。
然后我们跳过指针 指向的字符，用指针 继续向右移动，直到 指向的字符与 指向的字符不同，此时我们得到了一个长度为 的子串 ，其中所有字符都相同。那么我们最多通过一次交换操作，可以得到的最长单字符重复子串的长度为 。接下来，我们将指针 移动到 ，继续寻找下一个子串。我们取所有满足条件的子串的最大长度即可。
时间复杂度为 ，空间复杂度 。其中 为字符串的长度；而 为字符集的大小，本题中 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each character is processed in run-length encoding and during the sliding window merge. Space complexity is O(n) for storing blocks and O(1) for the fixed alphabet frequency map. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate identifies that only one swap is allowed and explains its effect on repeated substrings.
- question_mark
Look for recognition that blocks of the same character separated by one different character can be merged strategically.
- question_mark
Listen for a plan that uses linear scanning or sliding window rather than brute force substring checks.
常见陷阱
外企场景- error
Failing to consider merging non-contiguous blocks separated by a single character.
- error
Ignoring the case when all characters are identical and no swap is needed.
- error
Overcomplicating the solution with nested loops instead of using run-length encoding and sliding window.
进阶变体
外企场景- arrow_right_alt
Allow multiple swaps and compute the longest repeated substring achievable with k swaps.
- arrow_right_alt
Return the starting and ending indices of the maximum repeated substring after one swap.
- arrow_right_alt
Compute the longest repeated substring after swaps for uppercase and lowercase characters with different case sensitivity rules.