class Solution {
public:
int countCompleteSubstrings(string word, int k) {
}
};
100145. 统计完全子字符串
给你一个字符串 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原站题解
python3 解法, 执行用时: 7032 ms, 内存消耗: 16.6 MB, 提交时间: 2023-12-03 22:48:02
'''
相邻字母相差至多为2，这个约束把word划分成了多个子串s，每个子串分别处理。
可以用分组循环找到每个子串s。
对于每个子串，由于每个字符恰好出现k次，我们可以枚举有m种字符。问题变成：
长度固定位m*k的滑动窗口，判断每种字符是否都恰好出现了k次。
'''
class Solution:
def countCompleteSubstrings(self, word: str, k: int) -> int:
def f(s: str) -> int:
res = 0
for m in range(1, 27):
if k * m > len(s):
break
cnt = Counter()
for right, c in enumerate(s):
cnt[c] += 1
left = right + 1 - k * m
if left >= 0:
res += all(c == 0 or c == k for c in cnt.values())
cnt[s[left]] -= 1
return res
n = len(word)
ans = i = 0
while i < n:
st = i
i += 1
while i < n and abs(ord(word[i]) - ord(word[i - 1])) <= 2:
i += 1
ans += f(word[st:i])
return ans
java 解法, 执行用时: 88 ms, 内存消耗: 43.4 MB, 提交时间: 2023-12-03 22:48:14
class Solution {
public int countCompleteSubstrings(String word, int k) {
int n = word.length();
int ans = 0;
for (int i = 0; i < n; ) {
int st = i;
for (i++; i < n && Math.abs(word.charAt(i) - word.charAt(i - 1)) <= 2; i++) ;
ans += f(word.substring(st, i), k);
}
return ans;
}
private int f(String S, int k) {
char[] s = S.toCharArray();
int res = 0;
for (int m = 1; m <= 26 && k * m <= s.length; m++) {
int[] cnt = new int[26];
for (int right = 0; right < s.length; right++) {
cnt[s[right] - 'a']++;
int left = right + 1 - k * m;
if (left >= 0) {
boolean ok = true;
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0 && cnt[i] != k) {
ok = false;
break;
}
}
if (ok) res++;
cnt[s[left] - 'a']--;
}
}
}
return res;
}
}
cpp 解法, 执行用时: 152 ms, 内存消耗: 17.8 MB, 提交时间: 2023-12-03 22:48:29
class Solution {
int f(string s, int k) {
int res = 0;
for (int m = 1; m <= 26 && k * m <= s.length(); m++) {
int cnt[26]{};
auto check = [&]() {
for (int i = 0; i < 26; i++) {
if (cnt[i] && cnt[i] != k) {
return;
}
}
res++;
};
for (int right = 0; right < s.length(); right++) {
cnt[s[right] - 'a']++;
int left = right + 1 - k * m;
if (left >= 0) {
check();
cnt[s[left] - 'a']--;
}
}
}
return res;
}
public:
int countCompleteSubstrings(string word, int k) {
int n = word.length();
int ans = 0;
for (int i = 0; i < n;) {
int st = i;
for (i++; i < n && abs(int(word[i]) - int(word[i - 1])) <= 2; i++);
ans += f(word.substr(st, i - st), k);
}
return ans;
}
};
golang 解法, 执行用时: 64 ms, 内存消耗: 6.2 MB, 提交时间: 2023-12-03 22:49:09
func f(s string, k int) (res int) {
for m := 1; m <= 26 && k*m <= len(s); m++ {
cnt := [26]int{}
check := func() {
for i := range cnt {
if cnt[i] > 0 && cnt[i] != k {
return
}
}
res++
}
for right, in := range s {
cnt[in-'a']++
if left := right + 1 - k*m; left >= 0 {
check()
cnt[s[left]-'a']--
}
}
}
return
}
func countCompleteSubstrings(word string, k int) (ans int) {
for i, n := 0, len(word); i < n; {
st := i
for i++; i < n && abs(int(word[i])-int(word[i-1])) <= 2; i++ {
}
ans += f(word[st:i], k)
}
return
}
func abs(x int) int { if x < 0 { return -x }; return x }