Count Good Substrings
In customer support systems, analyzing interaction logs is crucial for identifying patterns and ensuring quality service. One common task involves scanning textual data for "good" segments that adhere to specific content policies. For instance, a policy might dictate that no single character should appear excessively within a short text snippet to avoid spam-like patterns or keyword stuffing. This problem asks you to identify and count all such valid substrings within a given log entry.
You are given a string s and an integer k. Your task is to implement a function that returns the total number of "good" substrings of s. A substring is considered "good" if the frequency of every character within that substring is at most k.
s: A string representing the main log entry. It will consist of lowercase English letters.k: An integer representing the maximum allowed frequency for any character within a "good" substring.s should result in 0 good substrings.k >= 1.k will always be a positive integer.s will only contain lowercase English letters ('a' through 'z').Examples
Example 1
Input:
s = "aab", k = 1
Output:
4
Note:
The good substrings are: "a" (at index 0), "a" (at index 1), "b" (at index 2), "ab" (from index 1 to 2). The substring "aa" is not good because 'a' appears 2 times, which exceeds k=1. Similarly, "aab" is not good.
Example 2
Input:
s = "aaabbc", k = 2
Output:
17
Note:
Example substrings: "a", "aa", "b", "bb", "c", "ab", "aab", "abb", "bbc", "aabb", "abbc", "aabbc" are all good. Substrings like "aaa" or "aaabb" are not good because 'a' appears 3 times, exceeding k=2.
Example 3
Input:
s = "abc", k = 1
Output:
6
Note:
All substrings are good because each character appears at most once (which is <= k=1). The good substrings are: "a", "b", "c", "ab", "bc", "abc".
Constraints
1 <= s.length <= 10^51 <= k <= s.lengths consists of only lowercase English letters.Loading editor...