题目描述
给你一个仅由小写英文字母组成的字符串 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 <= 50s 仅由小写英文字母组成。
解法
方法一：二分查找 + 滑动窗口计数
我们注意到，如果一个长度为 $x$ 且出现至少三次的特殊子字符串存在，那么长度为 $x-1$ 的特殊子字符串也一定存在，这存在着单调性，因此我们可以使用二分查找的方法来找到最长的特殊子字符串。
我们定义二分查找的左边界 $l = 0$，右边界 $r = n$，其中 $n$ 是字符串的长度。每次二分查找的过程中，我们取 $mid = \lfloor \frac{l + r + 1}{2} \rfloor$，如果长度为 $mid$ 的特殊子字符串存在，那么我们就将左边界更新为 $mid$，否则我们就将右边界更新为 $mid - 1$。在二分查找的过程中，我们使用滑动窗口来计算特殊子字符串的个数。
具体地，我们设计一个函数 $check(x)$，表示长度为 $x$ 且出现至少三次的特殊子字符串是否存在。
在函数 $check(x)$ 中，我们定义一个哈希表或长度为 $26$ 的数组 $cnt$，其中 $cnt[i]$ 表示长度为 $x$，且由第 $i$ 个小写字母组成的特殊子字符串的个数。我们遍历字符串 $s$，如果当前遍历到的字符为 $s[i]$，那么我们将指针 $j$ 向右移动，直到 $s[j] \neq s[i]$，此时 $s[i \cdots j-1]$ 就是一个长度为 $x$ 的特殊子字符串，我们将 $cnt[s[i]]$ 增加 $\max(0, j - i - x + 1)$，然后将指针 $i$ 更新为 $j$。
在遍历结束之后，我们遍历数组 $cnt$，如果存在 $cnt[i] \geq 3$，那么就说明长度为 $x$ 且出现至少三次的特殊子字符串存在，我们返回 $true$，否则返回 $false$。
时间复杂度 $O((n + |\Sigma|) \times \log n)$，空间复杂度 $O(|\Sigma|)$，其中 $n$ 是字符串 $s$ 的长度，而 $|\Sigma|$ 表示字符集的大小，本题中字符集为小写英文字母，因此 $|\Sigma| = 26$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | class Solution {
private String s;
private int n;
public int maximumLength(String s) {
this.s = s;
n = s.length();
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l == 0 ? -1 : l;
}
private boolean check(int x) {
int[] cnt = new int[26];
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int k = s.charAt(i) - 'a';
cnt[k] += Math.max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution {
public:
int maximumLength(string s) {
int n = s.size();
int l = 0, r = n;
auto check = [&](int x) {
int cnt[26]{};
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && s[j] == s[i]) {
++j;
}
int k = s[i] - 'a';
cnt[k] += max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
};
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l == 0 ? -1 : l;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | func maximumLength(s string) int {
n := len(s)
l, r := 0, n
check := func(x int) bool {
cnt := [26]int{}
for i := 0; i < n; {
j := i + 1
for j < n && s[j] == s[i] {
j++
}
k := s[i] - 'a'
cnt[k] += max(0, j-i-x+1)
if cnt[k] >= 3 {
return true
}
i = j
}
return false
}
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
if l == 0 {
return -1
}
return l
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | function maximumLength(s: string): number {
const n = s.length;
let [l, r] = [0, n];
const check = (x: number): boolean => {
const cnt: number[] = Array(26).fill(0);
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && s[j] === s[i]) {
j++;
}
const k = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
cnt[k] += Math.max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
};
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l === 0 ? -1 : l;
}
|
方法二：计数
时间复杂度 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | function maximumLength(s: string): number {
const cnt = new Map<string, number>();
const n = s.length;
let [c, ch] = [0, ''];
for (let i = 0; i < n + 1; i++) {
if (ch === s[i]) {
c++;
} else {
let j = 1;
while (c) {
const char = ch.repeat(j++);
cnt.set(char, (cnt.get(char) ?? 0) + c);
c--;
}
ch = s[i];
c = 1;
}
}
let res = -1;
for (const [x, c] of cnt) {
if (c >= 3) {
res = Math.max(res, x.length);
}
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | function maximumLength(s) {
const cnt = new Map();
const n = s.length;
let [c, ch] = [0, ''];
for (let i = 0; i < n + 1; i++) {
if (ch === s[i]) {
c++;
} else {
let j = 1;
while (c) {
const char = ch.repeat(j++);
cnt.set(char, (cnt.get(char) ?? 0) + c);
c--;
}
ch = s[i];
c = 1;
}
}
let res = -1;
for (const [x, c] of cnt) {
if (c >= 3) {
res = Math.max(res, x.length);
}
}
return res;
}
|