题目描述
给你一个字符串 word 和一个整数 k 。
如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：
s 中每个字符 恰好 出现 k 次。- 相邻字符在字母表中的顺序 至多 相差
2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差 至多 为 2 。
请你返回 word 中 完全 子字符串的数目。
子字符串 指的是一个字符串中一段连续 非空 的字符序列。
示例 1：
输入：word = "igigee", k = 2
输出：3
解释：完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：igigee, igigee, igigee 。
示例 2：
输入：word = "aaabbbccc", k = 3
输出：6
解释：完全子字符串需要满足每个字符恰好出现 3 次，且相邻字符相差至多为 2 ：aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。
提示：
1 <= word.length <= 105word 只包含小写英文字母。1 <= k <= word.length
解法
方法一：枚举字符种类数 + 滑动窗口
根据题目描述中的条件 $2$，我们可以发现，一个完全字符串中，相邻两个字符之差不超过 $2$。因此，我们遍历字符串 $word$，可以利用双指针把 $word$ 分割成若干个子字符串，这些子字符串中的字符种类数不超过 $26$，且相邻字符之差不超过 $2$。接下来，我们只需要在每个子字符串中，统计每个字符都出现 $k$ 次的子字符串的个数即可。
我们定义一个函数 $f(s)$，它的功能是统计字符串 $s$ 中每个字符都出现 $k$ 次的子字符串的个数。由于 $s$ 中的字符种类数不超过 $26$，因此我们可以枚举每个字符种类数 $i$，其中 $1 \le i \le 26$，那么每个字符种类数为 $i$ 的子字符串的长度为 $l = i \times k$。
我们可以用一个数组或哈希表 $cnt$ 维护一个长度为 $l$ 的滑动窗口中每个字符出现的次数，用另一个哈希表 $freq$ 维护每个次数出现的次数。如果 $freq[k] = i$，即有 $i$ 个字符都出现了 $k$ 次，那么我们就找到了一个满足条件的子字符串。我们可以用双指针维护这个滑动窗口，每次移动右指针时，我们将右指针指向的字符出现的次数加一，并更新 $freq$ 数组；每次移动左指针时，我们将左指针指向的字符出现的次数减一，并更新 $freq$ 数组。在每次移动指针后，我们都判断 $freq[k]$ 是否等于 $i$，如果等于则说明我们找到了一个满足条件的子字符串。
时间复杂度 $O(n \times |\Sigma|)$，空间复杂度 $O(|\Sigma|)$，其中 $n$ 是字符串 $word$ 的长度；而 $\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
23
24
25
26
27
28
29
30
31
32
33 | class Solution:
def countCompleteSubstrings(self, word: str, k: int) -> int:
def f(s: str) -> int:
m = len(s)
ans = 0
for i in range(1, 27):
l = i * k
if l > m:
break
cnt = Counter(s[:l])
freq = Counter(cnt.values())
ans += freq[k] == i
for j in range(l, m):
freq[cnt[s[j]]] -= 1
cnt[s[j]] += 1
freq[cnt[s[j]]] += 1
freq[cnt[s[j - l]]] -= 1
cnt[s[j - l]] -= 1
freq[cnt[s[j - l]]] += 1
ans += freq[k] == i
return ans
n = len(word)
ans = i = 0
while i < n:
j = i + 1
while j < n and abs(ord(word[j]) - ord(word[j - 1])) <= 2:
j += 1
ans += f(word[i:j])
i = j
return ans
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | class Solution {
public int countCompleteSubstrings(String word, int k) {
int n = word.length();
int ans = 0;
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && Math.abs(word.charAt(j) - word.charAt(j - 1)) <= 2) {
++j;
}
ans += f(word.substring(i, j), k);
i = j;
}
return ans;
}
private int f(String s, int k) {
int m = s.length();
int ans = 0;
for (int i = 1; i <= 26 && i * k <= m; ++i) {
int l = i * k;
int[] cnt = new int[26];
for (int j = 0; j < l; ++j) {
++cnt[s.charAt(j) - 'a'];
}
Map<Integer, Integer> freq = new HashMap<>();
for (int x : cnt) {
if (x > 0) {
freq.merge(x, 1, Integer::sum);
}
}
if (freq.getOrDefault(k, 0) == i) {
++ans;
}
for (int j = l; j < m; ++j) {
int a = s.charAt(j) - 'a';
int b = s.charAt(j - l) - 'a';
freq.merge(cnt[a], -1, Integer::sum);
++cnt[a];
freq.merge(cnt[a], 1, Integer::sum);
freq.merge(cnt[b], -1, Integer::sum);
--cnt[b];
freq.merge(cnt[b], 1, Integer::sum);
if (freq.getOrDefault(k, 0) == i) {
++ans;
}
}
}
return ans;
}
}
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 | class Solution {
public:
int countCompleteSubstrings(string word, int k) {
int n = word.length();
int ans = 0;
auto f = [&](string s) {
int m = s.length();
int ans = 0;
for (int i = 1; i <= 26 && i * k <= m; ++i) {
int l = i * k;
int cnt[26]{};
for (int j = 0; j < l; ++j) {
++cnt[s[j] - 'a'];
}
unordered_map<int, int> freq;
for (int x : cnt) {
if (x > 0) {
freq[x]++;
}
}
if (freq[k] == i) {
++ans;
}
for (int j = l; j < m; ++j) {
int a = s[j] - 'a';
int b = s[j - l] - 'a';
freq[cnt[a]]--;
cnt[a]++;
freq[cnt[a]]++;
freq[cnt[b]]--;
cnt[b]--;
freq[cnt[b]]++;
if (freq[k] == i) {
++ans;
}
}
}
return ans;
};
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && abs(word[j] - word[j - 1]) <= 2) {
++j;
}
ans += f(word.substr(i, j - i));
i = j;
}
return ans;
}
};
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 | func countCompleteSubstrings(word string, k int) (ans int) {
n := len(word)
f := func(s string) (ans int) {
m := len(s)
for i := 1; i <= 26 && i*k <= m; i++ {
l := i * k
cnt := [26]int{}
for j := 0; j < l; j++ {
cnt[int(s[j]-'a')]++
}
freq := map[int]int{}
for _, x := range cnt {
if x > 0 {
freq[x]++
}
}
if freq[k] == i {
ans++
}
for j := l; j < m; j++ {
a := int(s[j] - 'a')
b := int(s[j-l] - 'a')
freq[cnt[a]]--
cnt[a]++
freq[cnt[a]]++
freq[cnt[b]]--
cnt[b]--
freq[cnt[b]]++
if freq[k] == i {
ans++
}
}
}
return
}
for i := 0; i < n; {
j := i + 1
for j < n && abs(int(word[j])-int(word[j-1])) <= 2 {
j++
}
ans += f(word[i:j])
i = j
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 | function countCompleteSubstrings(word: string, k: number): number {
const f = (s: string): number => {
const m = s.length;
let ans = 0;
for (let i = 1; i <= 26 && i * k <= m; i++) {
const l = i * k;
const cnt: number[] = new Array(26).fill(0);
for (let j = 0; j < l; j++) {
cnt[s.charCodeAt(j) - 'a'.charCodeAt(0)]++;
}
const freq: { [key: number]: number } = {};
for (const x of cnt) {
if (x > 0) {
freq[x] = (freq[x] || 0) + 1;
}
}
if (freq[k] === i) {
ans++;
}
for (let j = l; j < m; j++) {
const a = s.charCodeAt(j) - 'a'.charCodeAt(0);
const b = s.charCodeAt(j - l) - 'a'.charCodeAt(0);
freq[cnt[a]]--;
cnt[a]++;
freq[cnt[a]] = (freq[cnt[a]] || 0) + 1;
freq[cnt[b]]--;
cnt[b]--;
freq[cnt[b]] = (freq[cnt[b]] || 0) + 1;
if (freq[k] === i) {
ans++;
}
}
}
return ans;
};
let n = word.length;
let ans = 0;
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && Math.abs(word.charCodeAt(j) - word.charCodeAt(j - 1)) <= 2) {
j++;
}
ans += f(word.substring(i, j));
i = j;
}
return ans;
}
|