Frontend School

Count Good Substrings

DSA
medium

Count Good Substrings

Medium
Sliding Window
Frequency Map
String

Overview

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.

What you need to do / Task

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.

Input & output

  • Input:
    • 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.
  • Output:
    • An integer representing the total count of "good" substrings.

Clarifications

  • An empty string s should result in 0 good substrings.
  • A single character substring is always "good" if k >= 1.
  • k will always be a positive integer.
  • The string s will only contain lowercase English letters ('a' through 'z').

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 1 <= k <= s.length
  • s consists of only lowercase English letters.

Out of scope

  • Handling non-alphabetic characters or uppercase letters.
  • Optimizing for extremely large alphabets (e.g., Unicode characters beyond basic ASCII).
  • Case sensitivity (all inputs are lowercase).

What interviewers evaluate

  • Correctness: The solution accurately identifies and counts all good substrings according to the problem definition.
  • Efficiency: The algorithm demonstrates optimal time complexity (linear time O(N)) and reasonable space complexity for the given constraints.
  • Sliding Window Application: Effective use of the sliding window pattern, including proper window expansion, contraction, and maintenance of character frequencies.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable names and comments where necessary.

Loading editor...