题目描述
给你一个仅由小写英文字母组成的字符串 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 <= 5 * 105s 仅由小写英文字母组成。
解法
方法一：二分查找 + 滑动窗口计数
我们注意到，如果一个长度为 \(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;
}
|