题目描述
给你一个字符串 s
,请找出满足每个字符最多出现两次的最长子字符串,并返回该子字符串的 最大 长度。
样例
输入: s = "bcbbbcba"
输出: 4
解释:
以下子字符串长度为 4,并且每个字符最多出现两次:"bcbb(bcba)"。
输入: s = "aaaa"
输出: 2
解释:
以下子字符串长度为 2,并且每个字符最多出现两次:"(aa)aa"。
限制
2 <= s.length <= 100
s
仅由小写英文字母组成。
算法
(双指针) $O(n + |\Sigma|)$
- 对于每个区间右端点 $r$,找到尽可能小的区间左端点 $l$,使得区间 $[l, r]$ 满足条件。
- 注意到,$l$ 是随着 $r$ 单调不减的,所以可以使用双指针移动。
- 维护一个字符出现次数的数组,每次移动 $r$ 时,累加当前字符的出现次数。如果当前字符的出现次数超过了 2 次,则不断移动左端点,直到当前字符的出现次数小于等于 2,然后更新答案。
时间复杂度
- 定义字符出现次数数组的时间复杂度为 $O(|\Sigma|)$。
- 每个位置最多被遍历两次,故总时间复杂度为 $O(n + |\Sigma|)$。
空间复杂度
- 需要 $O(|\Sigma|)$ 的额外空间存储字符出现次数的数组。
C++ 代码
class Solution {
public:
int maximumLengthSubstring(string s) {
const int n = s.size();
vector<int> seen(26, 0);
int ans = 0;
for (int l = 0, r = 0; r < n; r++) {
int c = s[r] - 'a';
++seen[c];
while (seen[c] > 2) {
--seen[s[l] - 'a'];
++l;
}
ans = max(ans, r - l + 1);
}
return ans;
}
};