LeetCode 题解工作台
找出出现至少三次的最长特殊子字符串 II
给你一个仅由小写英文字母组成的字符串 s 。 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd" 、 "zz" 和 "f" 是特殊字符串。 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们注意到，如果一个长度为 且出现至少三次的特殊子字符串存在，那么长度为 的特殊子字符串也一定存在，这存在着单调性，因此我们可以使用二分查找的方法来找到最长的特殊子字符串。 我们定义二分查找的左边界 $l = 0$，右边界 $r = n$，其中 是字符串的长度。每次二分查找的过程中，我们取 $mid = \lfloor \frac{l + r + 1}{2} \rfloor$，如果长度为 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
示例 1：
输入：s = "aaaa" 输出：2 解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。 可以证明最大长度是 2 。
示例 2：
输入：s = "abcdef" 输出：-1 解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
示例 3：
输入：s = "abcaba" 输出：1 解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。 可以证明最大长度是 1 。
提示：
3 <= s.length <= 5 * 105s仅由小写英文字母组成。
解题思路
方法一：二分查找 + 滑动窗口计数
我们注意到，如果一个长度为 且出现至少三次的特殊子字符串存在，那么长度为 的特殊子字符串也一定存在，这存在着单调性，因此我们可以使用二分查找的方法来找到最长的特殊子字符串。
我们定义二分查找的左边界 ，右边界 ，其中 是字符串的长度。每次二分查找的过程中，我们取 ，如果长度为 的特殊子字符串存在，那么我们就将左边界更新为 ，否则我们就将右边界更新为 。在二分查找的过程中，我们使用滑动窗口来计算特殊子字符串的个数。
具体地，我们设计一个函数 ，表示长度为 且出现至少三次的特殊子字符串是否存在。
在函数 中，我们定义一个哈希表或长度为 的数组 ，其中 表示长度为 ，且由第 个小写字母组成的特殊子字符串的个数。我们遍历字符串 ，如果当前遍历到的字符为 ，那么我们将指针 向右移动，直到 ，此时 就是一个长度为 的特殊子字符串，我们将 增加 ，然后将指针 更新为 。
在遍历结束之后，我们遍历数组 ，如果存在 ，那么就说明长度为 且出现至少三次的特殊子字符串存在，我们返回 ，否则返回 。
时间复杂度 ，空间复杂度 ，其中 是字符串 的长度，而 表示字符集的大小，本题中字符集为小写英文字母，因此 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(c \cdot k) \approx O(1) |
面试官常问的追问
外企场景- question_mark
Can the candidate apply binary search effectively on the valid answer space?
- question_mark
Does the candidate optimize the substring check with hash tables and sliding windows?
- question_mark
How well does the candidate manage edge cases, such as strings without repeating substrings?
常见陷阱
外企场景- error
Failing to handle edge cases where no special substring occurs three times.
- error
Inefficiently checking all substrings without using binary search and hash tables.
- error
Overcomplicating the solution with unnecessary algorithms or data structures.
进阶变体
外企场景- arrow_right_alt
What if the problem asked for substrings that occur at least twice instead of three times?
- arrow_right_alt
What if the substring could be made up of more than one character?
- arrow_right_alt
What if the input string contained uppercase letters or was case-insensitive?