LeetCode 3325: Count Substrings With K-Frequency Characters I

Explanation

To solve this problem, we can iterate through all possible substrings of the given string s and count the frequency of each character. For each substring, we maintain a frequency map of characters. If at least one character appears at least k times in the substring, we increment the count of valid substrings. We can optimize this process by using sliding window technique to avoid redundant calculations.

Algorithm:

1. Initialize a variable count to store the total count of valid substrings.
2. Iterate through all possible substrings using a sliding window approach.
3. Maintain a frequency map of characters within the current window.
4. For each substring, check if at least one character appears at least k times.
5. If true, increment the count.
6. Continue sliding the window until all substrings are processed.
7. Return the count.

Time Complexity: O(n^2) where n is the length of the input string s. Space Complexity: O(n) where n is the length of the input string s.

class Solution {
    public int countKFreqSubstrings(String s, int k) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] freq = new int[26];
            for (int j = i; j < s.length(); j++) {
                freq[s.charAt(j) - 'a']++;
                if (hasKFreqChar(freq, k)) {
                    count++;
                }
            }
        }
        return count;
    }
    
    private boolean hasKFreqChar(int[] freq, int k) {
        for (int f : freq) {
            if (f >= k) {
                return true;
            }
        }
        return false;
    }
}