题目描述
给你一个下标从 0 开始的字符串 s
,这个字符串只包含 0
到 9
的数字字符。
如果一个字符串 t
中至多有一对相邻字符是相等的,那么称这个字符串是 半重复的。
请你返回 s
中最长 半重复 子字符串的长度。
一个 子字符串 是一个字符串中一段连续 非空 的字符。
样例
输入:s = "52233"
输出:4
解释:最长半重复子字符串是 "5223",子字符串从 i = 0 开始,在 j = 3 处结束。
输入:s = "5494"
输出:4
解释:s 就是一个半重复字符串,所以答案为 4。
输入:s = "1111111"
输出:2
解释:最长半重复子字符串是 "11",子字符串从 i = 0 开始,在 j = 1 处结束。
限制
1 <= s.length <= 50
'0' <= s[i] <= '9'
算法
(双指针) $O(n)$
- 对于每一个位置 $i$,都找到尽可能小的位置 $j$,满足区间 $[j, i]$ 中没有多次出现重复的相邻字符,使用 $[j, i]$ 的长度更新答案。
- 注意到,随着 $i$ 的增加,$j$ 是单调不减的, 所以可以使用双指针算法。
- 如果当前 $[j, i]$ 不满足要求,则不断移动 $j$ 使得区间重新满足要求。
时间复杂度
- 每个位置最多被遍历两次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int longestSemiRepetitiveSubstring(string s) {
int ans = 1, cnt = 0;
for (int i = 1, j = 0; i < s.size(); i++) {
if (s[i] == s[i - 1])
++cnt;
while (cnt > 1 && j < i) {
if (s[j] == s[j + 1])
--cnt;
++j;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};
你是出题人吗?为什么思路这么妙