题目描述
给你一个仅由小写英文字母组成的字符串 s
。
如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 "abc"
不是特殊字符串,而字符串 "ddd"
、"zz"
和 "f"
是特殊字符串。
返回在 s
中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出现至少三次的特殊子字符串,则返回 -1
。
子字符串 是字符串中的一个连续 非空 字符序列。
样例
输入:s = "aaaa"
输出:2
解释:出现三次的最长特殊子字符串是 "aa":子字符串 "(aa)aa"、"a(aa)a" 和 "aa(aa)"。
可以证明最大长度是 2。
输入:s = "abcdef"
输出:-1
解释:不存在出现至少三次的特殊子字符串。因此返回 -1。
输入:s = "abcaba"
输出:1
解释:出现三次的最长特殊子字符串是 "a":子字符串 "(a)bcaba"、"abc(a)ba" 和 "abcab(a)"。
可以证明最大长度是 1。
限制
3 <= s.length <= 5 * 10^5
s
仅由小写英文字母组成。
算法
(分类讨论) $O(|\Sigma| + n)$
- 使用滑动窗口遍历字符串,划分每一段连续的合法子串,并将合法子串的长度存储到对应的字符上。
- 对于某个字符来说,假设最大的三个长度分别为 $m1 \ge m2 \ge m3$,则可以根据这三个长度求出这个字符共享的最大答案:
- 如果 $m1 = m2 = m3$,则 $m1$ 就是最大长度。
- 如果 $m1 \ge 2$ 且 $m2 \ge m1 - 1$,则 $m1 - 1$ 就是最大长度。
- 否则,当 $m1 \ge 3$ 时,$m1 - 2$ 时最大长度。
- 分别对每个字符进行统计,得到最大的答案。
时间复杂度
- 需要定义一个长度为 $O(|\Sigma|)$ 的数组存储每种字符下所有合法的长度。
- 滑动窗口预处理的时间复杂度为 $O(n)$。
- 求答案的时间复杂度均摊为 $O(n)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(|\Sigma| + n)$ 的额外空间存储每个字符下的所有合法长度。
C++ 代码
class Solution {
public:
int maximumLength(string s) {
const int n = s.size();
vector<vector<int>> cnt(26);
for (int i = 1, j = 0; i <= n; i++) {
if (i < n && s[i] == s[j])
continue;
cnt[s[j] - 'a'].push_back(i - j);
j = i;
}
int ans = -1;
for (char c = 0; c < 26; c++) {
int m1 = 0, m2 = 0, m3 = 0;
for (int x : cnt[c]) {
if (x > m1) {
m3 = m2; m2 = m1; m1 = x;
} else if (x > m2) {
m3 = m2; m2 = x;
} else if (x > m3) {
m3 = x;
}
}
if (m1 >= 1 && m3 == m1) ans = max(ans, m1);
else if (m1 >= 2 && m2 >= m1 - 1) ans = max(ans, m1 - 1);
else if (m1 >= 3) ans = max(ans, m1 - 2);
}
return ans;
}
};