Substrings of length k with k-1 distinct elements

JavaView on GFG

Time: O(n)

Space: O(k)

Intuition

Count substrings of length k with exactly k-1 distinct characters. Sliding window.

Algorithm

1Fixed window of size k. Track distinct character count. When window has exactly k-1 distinct: count++.

Common Pitfalls

•Fixed-size sliding window. Update frequency map as window slides. O(n).

Substrings of length k with k-1 distinct elements.java

Java

// Approach: Sliding window of size k with frequency map. Count windows with exactly k-1 distinct characters.
// Time: O(n) Space: O(k)
import java.util.*;

class Solution {
    public int substrCount(String s, int k) {
        char[] arr = s.toCharArray();
        int count = 0;
        for (int i = 0; i <= arr.length - k; i++) {
            Set<Character> set = new HashSet<>();

            for (int j = i; j < i + k; j++)
                set.add(arr[j]);
                
            if (set.size() == k - 1)
                count++;
        }
        return count;
    }
}

Was this solution helpful?