README.md

2067. Number of Equal Count Substrings

English Version

题目描述

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 * 104
• 1 <= count <= 3 * 104
• s consists only of lowercase English letters.

解法

前缀和统计每个位置各个字母出现的次数。然后根据 count 枚举子字符串左右端点，check 是否满足条件，是则 ans 加 1。

最后返回 ans。

Python3

class Solution:
    def equalCountSubstrings(self, s: str, count: int) -> int:
        n = len(s)
        if count > n:
            return 0
        counter = [[0] * 26 for _ in range(n + 1)]

        def check(i, j):
            c1 = counter[i]
            c2 = counter[j + 1]
            for k in range(26):
                if c2[k] == 0 or c1[k] == c2[k]:
                    continue
                if c2[k] - c1[k] != count:
                    return False
            return True

        ans = 0
        for i, c in enumerate(s):
            idx = ord(c) - ord('a')
            for j in range(26):
                counter[i + 1][j] = counter[i][j]
            counter[i + 1][idx] = counter[i][idx] + 1
            l = 0
            for _ in range(26):
                l += count
                j = i - l + 1
                if j < 0:
                    break
                ans += check(j, i)
        return ans

Java

class Solution {
    public int equalCountSubstrings(String s, int count) {
        int n = s.length();
        if (count > n) {
            return 0;
        }
        int[][] counter = new int[n + 1][26];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int idx = s.charAt(i) - 'a';
            for (int j = 0; j < 26; ++j) {
                counter[i + 1][j] = counter[i][j];
            }
            counter[i + 1][idx] = counter[i][idx] + 1;
            int l = 0;
            for (int k = 0; k < 26; ++k) {
                l += count;
                int j = i - l + 1;
                if (j < 0) {
                    break;
                }
                ans += check(j, i, count, counter) ? 1 : 0;
            }
        }
        return ans;
    }

    private boolean check(int i, int j, int count, int[][] counter) {
        int[] c1 = counter[i];
        int[] c2 = counter[j + 1];
        for (int k = 0; k < 26; ++k) {
            if (c2[k] == 0 || c1[k] == c2[k]) {
                continue;
            }
            if (c2[k] - c1[k] != count) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    int equalCountSubstrings(string s, int count) {
        int n = s.size();
        if (count > n) return 0;
        vector<vector<int>> counter(n + 1, vector<int>(26));
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            int idx = s[i] - 'a';
            for (int j = 0; j < 26; ++j) counter[i + 1][j] = counter[i][j];
            counter[i + 1][idx] = counter[i][idx] + 1;
            int l = 0;
            for (int k = 0; k < 26; ++k)
            {
                l += count;
                int j = i - l + 1;
                if (j < 0) break;
                ans += check(j, i, count, counter);
            }
        }
        return ans;
    }

    bool check(int i, int j, int count, vector<vector<int>>& counter) {
        auto& c1 = counter[i];
        auto& c2 = counter[j + 1];
        for (int k = 0; k < 26; ++k)
        {
            if (c2[k] == 0 || c1[k] == c2[k]) continue;
            if (c2[k] - c1[k] != count) return false;
        }
        return true;
    }
};

Go

func equalCountSubstrings(s string, count int) int {
	n := len(s)
	if count > n {
		return 0
	}
	counter := make([][]int, n+1)
	for i := range counter {
		counter[i] = make([]int, 26)
	}
	ans := 0
	check := func(i, j int) bool {
		c1, c2 := counter[i], counter[j+1]
		for k := 0; k < 26; k++ {
			if c2[k] == 0 || c1[k] == c2[k] {
				continue
			}
			if c2[k]-c1[k] != count {
				return false
			}
		}
		return true
	}
	for i, c := range s {
		idx := c - 'a'
		for j := 0; j < 26; j++ {
			counter[i+1][j] = counter[i][j]
		}
		counter[i+1][idx] = counter[i][idx] + 1
		l := 0
		for k := 0; k < 26; k++ {
			l += count
			j := i - l + 1
			if j < 0 {
				break
			}
			if check(j, i) {
				ans++
			}
		}
	}
	return ans
}

...