题目描述
给你一个仅由小写英文字母组成的字符串 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 <= 50
s
仅由小写英文字母组成。
算法
(暴力枚举) $O(|\Sigma| + n^3)$
- 从大到小枚举目标长度,然后暴力枚举每个子串,判断此长度下是否存在 3 个或以上的合法子串。
时间复杂度
- 需要定义一个长度为 $O(|\Sigma|)$ 的数组存储每种字符作为合法子串的出现次数。
- 共有 $O(n)$ 个目标长度,每个长度下都有 $O(n)$ 个子串,每个子串都需要 $O(n)$ 的时间判断。
- 故总时间复杂度为 $O(|\Sigma| + n^3)$。
空间复杂度
- 仅需要 $O(|\Sigma|)$ 的额外空间存储子串。
C++ 代码
class Solution {
public:
int maximumLength(string s) {
const int n = s.size();
for (int len = n - 2; len >= 1; len--) {
vector<int> cnt(26, 0);
for (int i = 0; i < n - len + 1; i++) {
bool ok = true;
for (int j = i + 1; j < i + len; j++)
if (s[j] != s[i]) {
ok = false;
break;
}
if (ok) {
++cnt[s[i] - 'a'];
if (cnt[s[i] - 'a'] >= 3)
return len;
}
}
}
return -1;
}
};