LeetCode 3329: Count Substrings With K-Frequency Characters II

Explanation:

To solve this problem, we can use a sliding window technique combined with a hashmap to track the frequency of characters in the substring. We will iterate over each character in the string and maintain a window of characters that have a frequency at least k. As we move the right pointer of the window, we will update the frequency of characters. If a character's frequency drops below k, we will shrink the window from the left until all characters in the window have a frequency of at least k.

After each window adjustment, we can count the number of substrings that satisfy the condition of having exactly k distinct characters. To count the number of substrings efficiently, we can keep track of the number of valid substrings that end at each index.

Finally, we sum up the counts of valid substrings for all possible windows to get the total count of substrings with exactly k distinct characters.

Time Complexity:

The time complexity of this approach is O(N^2) where N is the length of the input string. This is because for each character in the string, we might need to iterate over all characters in the window to update frequencies and check the validity of substrings.

Space Complexity:

The space complexity of this approach is O(N) to store the hashmap for tracking character frequencies.

:

class Solution {
    public int countkDist(String s, int k) {
        int result = 0;
        for(int i = 1; i <= 26; i++) {
            result += atMostKDistinct(s, i, k) - atMostKDistinct(s, i - 1, k);
        }
        return result;
    }
    
    private int atMostKDistinct(String s, int maxUnique, int k) {
        int[] count = new int[26];
        int left = 0, right = 0;
        int uniqueChars = 0, countAtMostK = 0;
        
        while(right < s.length()) {
            if(count[s.charAt(right) - 'a'] == 0) {
                uniqueChars++;
            }
            count[s.charAt(right) - 'a']++;
            right++;
            
            while(uniqueChars > maxUnique) {
                count[s.charAt(left) - 'a']--;
                if(count[s.charAt(left) - 'a'] == 0) {
                    uniqueChars--;
                }
                left++;
            }
            if(uniqueChars <= maxUnique) {
                countAtMostK += right - left;
            }
        }
        return countAtMostK;
    }
}