2067. Number of Equal Count Substrings π ο
Descriptionο
You are given a 0-indexed string s consisting of only lowercase English letters, and an integer count. A substring of s is said to be an equal count substring if, for each unique letter in the substring, it appears exactly count times in the substring.
Return the number of equal count substrings in s.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "aaabcbbcc", count = 3 Output: 3 Explanation: The substring that starts at index 0 and ends at index 2 is "aaa". The letter 'a' in the substring appears exactly 3 times. The substring that starts at index 3 and ends at index 8 is "bcbbcc". The letters 'b' and 'c' in the substring appear exactly 3 times. The substring that starts at index 0 and ends at index 8 is "aaabcbbcc". The letters 'a', 'b', and 'c' in the substring appear exactly 3 times.
Example 2:
Input: s = "abcd", count = 2 Output: 0 Explanation: The number of times each letter appears in s is less than count. Therefore, no substrings in s are equal count substrings, so return 0.
Example 3:
Input: s = "a", count = 5 Output: 0 Explanation: The number of times each letter appears in s is less than count. Therefore, no substrings in s are equal count substrings, so return 0
Constraints:
1 <= s.length <= 3 * 1041 <= count <= 3 * 104sconsists only of lowercase English letters.
Solutionsο
Solution 1: Enumeration + Sliding Windowο
We can enumerate the number of types of letters in the substring within the range of $[1..26]$, then the length of the substring is $i \times count$.
Next, we take the current substring length as the size of the window, count the number of types of letters in the window size that are equal to $count$, and record it in $t$. If $i = t$ at this time, it means that the number of letters in the current window are all $count$, then we can increment the answer by one.
The time complexity is $O(n \times C)$, and the space complexity is $O(C)$. Where $n$ is the length of the string $s$, and $C$ is the number of types of letters, in this problem $C = 26$.
Python3ο
class Solution:
def equalCountSubstrings(self, s: str, count: int) -> int:
ans = 0
for i in range(1, 27):
k = i * count
if k > len(s):
break
cnt = Counter()
t = 0
for j, c in enumerate(s):
cnt[c] += 1
t += cnt[c] == count
t -= cnt[c] == count + 1
if j >= k:
cnt[s[j - k]] -= 1
t += cnt[s[j - k]] == count
t -= cnt[s[j - k]] == count - 1
ans += i == t
return ans
Javaο
class Solution {
public int equalCountSubstrings(String s, int count) {
int ans = 0;
int[] cnt = new int[26];
int n = s.length();
for (int i = 1; i < 27 && i * count <= n; ++i) {
int k = i * count;
Arrays.fill(cnt, 0);
int t = 0;
for (int j = 0; j < n; ++j) {
int a = s.charAt(j) - 'a';
++cnt[a];
t += cnt[a] == count ? 1 : 0;
t -= cnt[a] == count + 1 ? 1 : 0;
if (j - k >= 0) {
int b = s.charAt(j - k) - 'a';
--cnt[b];
t += cnt[b] == count ? 1 : 0;
t -= cnt[b] == count - 1 ? 1 : 0;
}
ans += i == t ? 1 : 0;
}
}
return ans;
}
}
C++ο
class Solution {
public:
int equalCountSubstrings(string s, int count) {
int ans = 0;
int n = s.size();
int cnt[26];
for (int i = 1; i < 27 && i * count <= n; ++i) {
int k = i * count;
memset(cnt, 0, sizeof(cnt));
int t = 0;
for (int j = 0; j < n; ++j) {
int a = s[j] - 'a';
t += ++cnt[a] == count;
t -= cnt[a] == count + 1;
if (j >= k) {
int b = s[j - k] - 'a';
t += --cnt[b] == count;
t -= cnt[b] == count - 1;
}
ans += i == t;
}
}
return ans;
}
};
Goο
func equalCountSubstrings(s string, count int) (ans int) {
n := len(s)
for i := 1; i < 27 && i*count <= n; i++ {
k := i * count
cnt := [26]int{}
t := 0
for j, c := range s {
a := c - 'a'
cnt[a]++
if cnt[a] == count {
t++
} else if cnt[a] == count+1 {
t--
}
if j >= k {
b := s[j-k] - 'a'
cnt[b]--
if cnt[b] == count {
t++
} else if cnt[b] == count-1 {
t--
}
}
if i == t {
ans++
}
}
}
return
}
TypeScriptο
function equalCountSubstrings(s: string, count: number): number {
const n = s.length;
let ans = 0;
for (let i = 1; i < 27 && i * count <= n; ++i) {
const k = i * count;
const cnt: number[] = Array(26).fill(0);
let t = 0;
for (let j = 0; j < n; ++j) {
const a = s.charCodeAt(j) - 97;
t += ++cnt[a] === count ? 1 : 0;
t -= cnt[a] === count + 1 ? 1 : 0;
if (j >= k) {
const b = s.charCodeAt(j - k) - 97;
t += --cnt[b] === count ? 1 : 0;
t -= cnt[b] === count - 1 ? 1 : 0;
}
ans += i === t ? 1 : 0;
}
}
return ans;
}
JavaScriptο
/**
* @param {string} s
* @param {number} count
* @return {number}
*/
var equalCountSubstrings = function (s, count) {
const n = s.length;
let ans = 0;
for (let i = 1; i < 27 && i * count <= n; ++i) {
const k = i * count;
const cnt = Array(26).fill(0);
let t = 0;
for (let j = 0; j < n; ++j) {
const a = s.charCodeAt(j) - 97;
t += ++cnt[a] === count ? 1 : 0;
t -= cnt[a] === count + 1 ? 1 : 0;
if (j >= k) {
const b = s.charCodeAt(j - k) - 97;
t += --cnt[b] === count ? 1 : 0;
t -= cnt[b] === count - 1 ? 1 : 0;
}
ans += i === t ? 1 : 0;
}
}
return ans;
};