Count Number of Substrings with Exactly K Distinct Characters

Introduction

• Given a string of lowercase alphabets, the goal is to count all possible substrings that have exactly K distinct characters.

Key Definitions

• Distinct Characters: Different characters present in a substring. Example: In 'aaa', the number of distinct characters is 1 (only 'a').

Problem Examples

1. Example 1:

   • Input: "aba", K = 2
   • Substrings with exactly two distinct characters:
     • "ab"
     • "ba"
     • "aba"
   • Output: 3

2. Example 2:

   • Input: "abaca", K = 1
   • Substrings with exactly one distinct character:
     • "a", "b", "c", and also "aa"
   • Output: 7

Function to Implement

• Function: substring_count(s: str, K: int) -> int
• Returns: Count of substrings with exactly K distinct characters.

Time Complexity

• Expected time complexity: O(N)
• Auxiliary space: O(1)

Brute Force Approach

• Count distinct characters for all possible substrings.
• Complexity: O(N^2) (too slow)

Improved Approach

• Count of substrings with exactly K distinct characters can be derived from:
  • Count of substrings with at least K distinct characters
  • Count of substrings with at least K + 1 distinct characters
• Formula: exactly K = at least K - at least (K + 1)

Counting Substrings with At Least K Distinct Characters

1. Two pointers technique:
   • Use pointers L (start index) and R (end index) to find substrings.
   • Increment R to find the first index where the number of distinct characters >= K.
   • Calculate how many substrings start from L with this count.
2. Maintaining Distinct Count:
   • Use an array to track counts of characters from 'a' to 'z'.
   • Maintain a counter for the number of distinct characters.

Implementation Steps

1. Implement the main function.
2. Call a helper function that counts substrings with at least P distinct characters.
3. Subtract the two counts to get the answer.

Code Implementation

• Example Code: def substring_count(s: str, K: int) -> int: return count_substrings_at_least_k(s, K) - count_substrings_at_least_k(s, K + 1)

Conclusion

• By using the optimized approach with two pointers and efficient counting, the problem can be solved more effectively compared to the brute-force method.
• Final submission showed the problem was solved successfully.