README.md

2067. 等计数子串的数量

English Version

题目描述

给你一个下标从 0 开始的字符串 s，只包含小写英文字母和一个整数 count。如果 s 的 子串 中的每种字母在子串中恰好出现 count 次，这个子串就被称为 等计数子串。

返回 s 中 等计数子串 的个数。

子串 是字符串中连续的非空字符序列。

 

示例 1:

输入: s = "aaabcbbcc", count = 3
输出: 3
解释:
从下标 0 开始到下标 2 结束的子串是 "aaa"。
字母 “a” 在子串中恰好出现了 3 次。
从下标 3 开始到下标 8 结束的子串是 "bcbbcc"。
字母 “b” 和 “c” 在子串中恰好出现了 3 次。
从下标 0 开始到下标 8 结束的子串是 "aaabcbbcc"。
字母 “a”、“b” 和 “c” 在子串中恰好出现了 3 次。

示例 2:

输入: s = "abcd", count = 2
输出: 0
解释:
每种字母在 s 中出现的次数小于 count。
因此，s 中没有子串是等计数子串，返回 0。

示例 3:

输入: s = "a", count = 5
输出: 0
解释:
每种字母在 s 中出现的次数小于 count。
因此，s 中没有子串是等计数子串，返回 0。

 

提示:

• 1 <= s.length <= 3 * 104
• 1 <= count <= 3 * 104
• s 只由小写英文字母组成。

解法

方法一：枚举 + 滑动窗口

我们可以在 $[1..26]$ 范围内枚举子串的字母种类数 $x$，那么子串长度就是 $count \times x$。

接下来，我们将当前子串长度作为窗口的大小，统计窗口大小中有多少种字母的个数为 $count$，记录在 $y$ 中。如果此时 $x = y$，说明当前窗口中的字母个数都为 $count$，那么就可以将答案加一。

时间复杂度 $O(n \times C)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 为字母的种类数，本题中 $C = 26$。

Python3

class Solution:
    def equalCountSubstrings(self, s: str, count: int) -> int:
        ans = 0
        for x in range(1, 27):
            m = count * x
            if m > len(s):
                break
            cnt = Counter()
            y = 0
            for i, c in enumerate(s):
                cnt[c] += 1
                y += cnt[c] == count
                y -= cnt[c] == count + 1
                j = i - m
                if j >= 0:
                    cnt[s[j]] -= 1
                    y += cnt[s[j]] == count
                    y -= cnt[s[j]] == count - 1
                ans += x == y
        return ans

Java

class Solution {
    public int equalCountSubstrings(String s, int count) {
        int ans = 0;
        int n = s.length();
        for (int x = 1; x < 27 && count * x <= n; ++x) {
            int m = count * x;
            int[] cnt = new int[26];
            int y = 0;
            for (int i = 0; i < n; ++i) {
                int a = s.charAt(i) - 'a';
                ++cnt[a];
                if (cnt[a] == count) {
                    ++y;
                }
                if (cnt[a] == count + 1) {
                    --y;
                }
                int j = i - m;
                if (j >= 0) {
                    int b = s.charAt(j) - 'a';
                    --cnt[b];
                    if (cnt[b] == count) {
                        ++y;
                    }
                    if (cnt[b] == count - 1) {
                        --y;
                    }
                }
                if (x == y) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int equalCountSubstrings(string s, int count) {
        int ans = 0;
        int n = s.size();
        int cnt[26];
        for (int x = 1; x < 27 && count * x <= n; ++x) {
            int m = count * x;
            memset(cnt, 0, sizeof cnt);
            int y = 0;
            for (int i = 0; i < n; ++i) {
                int a = s[i] - 'a';
                ++cnt[a];
                y += cnt[a] == count;
                y -= cnt[a] == count + 1;
                int j = i - m;
                if (j >= 0) {
                    int b = s[j] - 'a';
                    --cnt[b];
                    y += cnt[b] == count;
                    y -= cnt[b] == count - 1;
                }
                ans += x == y;
            }
        }
        return ans;
    }
};

Go

func equalCountSubstrings(s string, count int) (ans int) {
	n := len(s)
	for x := 1; x < 27 && x*count <= n; x++ {
		m := x * count
		y := 0
		cnt := [26]int{}
		for i, c := range s {
			a := c - 'a'
			cnt[a]++
			if cnt[a] == count {
				y++
			}
			if cnt[a] == count+1 {
				y--
			}
			j := i - m
			if j >= 0 {
				b := s[j] - 'a'
				cnt[b]--
				if cnt[b] == count {
					y++
				}
				if cnt[b] == count-1 {
					y--
				}
			}
			if x == y {
				ans++
			}
		}
	}
	return
}

JavaScript

/**
 * @param {string} s
 * @param {number} count
 * @return {number}
 */
var equalCountSubstrings = function (s, count) {
    let ans = 0;
    const n = s.length;
    for (let x = 1; x <= 26 && x * count <= n; ++x) {
        const m = x * count;
        const cnt = new Array(26).fill(0);
        let y = 0;
        for (let i = 0; i < n; ++i) {
            const a = s.charCodeAt(i) - 'a'.charCodeAt(0);
            ++cnt[a];
            y += cnt[a] == count;
            y -= cnt[a] == count + 1;
            const j = i - m;
            if (j >= 0) {
                const b = s.charCodeAt(j) - 'a'.charCodeAt(0);
                --cnt[b];
                y += cnt[b] == count;
                y -= cnt[b] == count - 1;
            }
            ans += x == y;
        }
    }
    return ans;
};

...