Substrings with K Distinct

JavaView on GFG

Time: O(n)

Space: O(k)

Intuition

Count substrings with exactly k distinct characters. atMost(k) - atMost(k-1).

Algorithm

1atMost(k): sliding window counting subarrays with at most k distinct chars. Exactly k = atMost(k) - atMost(k-1).

Common Pitfalls

•Same as LC 992. Two sliding window calls. O(n) total.

Substrings with K Distinct.java

Java

// Approach: Sliding window with at-most-k trick: atMost(k) - atMost(k-1) gives exactly-k.
// Time: O(n) Space: O(k)
class Solution {
    int countSubstr(String s, int k) {
        return (int) (calcCount(s, k) - calcCount(s, k - 1));
    }

    long calcCount(String s, int k) {
        // Using Sliding Window Approach
        int i = 0;
        int j = 0;
        int n = s.length();
        int[] charFreq = new int[26];
        int dist_count = 0;
        long ans = 0;
        while (j < n) {
            charFreq[s.charAt(j) - 'a']++;
            if (charFreq[s.charAt(j) - 'a'] == 1) // Distinct Character
                dist_count++;

            // Decreasing Window Size
            while (dist_count > k) {
                charFreq[s.charAt(i) - 'a']--;
                if (charFreq[s.charAt(i) - 'a'] == 0)
                    dist_count--;
                i++;
            }
            j++;
            ans += (j - i + 1);
        }
        return ans;
    }
}

Was this solution helpful?