Explorer
Data Structures & Algorithms

Count all substrings with exactly k distinct characters using sliding window.

Problem Statement

Given a string `s` of lowercase alphabets, count all possible substrings that have exactly `k` distinct characters.

Examples

Input: s = "aba", k = 2

Output: 3

Explanation: Substrings with 2 distinct characters: "ab", "ba", "aba".

Input: s = "abaaca", k = 1

Output: 7

Explanation: Combining the input according to Count Number of Substrings logic yields 7.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: Counting substrings with exactly K distinct characters directly with sliding window is tricky. šŸ’” Hint 2: Use the identity: exactly(K) = atMost(K) - atMost(K - 1). šŸ’” Hint 3: atMost(K) is solved cleanly in O(N) using a standard sliding window.

Editorial & Approach

Problem Overview & Intuition

Counting substrings with exactly K distinct characters is equivalent to: (number of substrings with at most K distinct characters) - (number of substrings with at most K - 1 distinct characters). atMost(K) is computable in linear time via sliding window.

Step-by-Step Approach

  1. Define helper atMost(targetK) using two pointers left and right.
  2. Expand right, adding s[right] to frequency map.
  3. While map.size > targetK, shrink from left.
  4. Add right - left + 1 to count at each step.
  5. Return atMost(k) - atMost(k - 1).

Optimal Implementation (JavaScript)

function countSubstringsWithKDistinct(s, k) {
  function atMost(targetK) {
    if (targetK <= 0) return 0;
    const freq = new Map();
    let left = 0, count = 0;
    for (let right = 0; right < s.length; right++) {
      freq.set(s[right], (freq.get(s[right]) || 0) + 1);
      while (freq.size > targetK) {
        freq.set(s[left], freq.get(s[left]) - 1);
        if (freq.get(s[left]) === 0) freq.delete(s[left]);
        left++;
      }
      count += (right - left + 1);
    }
    return count;
  }
  return atMost(k) - atMost(k - 1);
}

Complexity Analysis

Time Complexity O(N) ā€” two sliding window passes over string.
Space Complexity O(1) ā€” alphabet map of size <= 26.

Edge Cases & Corner Traps Handled

  • k > number of unique characters in s: returns 0.
  • k = 1: counts substrings of identical characters.

Count Number of Substrings

Medium
Given a string `s` of lowercase alphabets, count all possible substrings that have exactly `k` distinct characters.
Example Scenarios
1Example 1
Input: s = "aba", k = 2
Output: 3
Explanation:

Substrings with 2 distinct characters: "ab", "ba", "aba".

2Example 2
Input: s = "abaaca", k = 1
Output: 7
Explanation:

Combining the input according to Count Number of Substrings logic yields 7.

Editor
Loading Editor...
s =
"pqpqs"
k =
2
Output:Click "Run" above to execute and verify your code here.
7