3325. Count Substrings With K-Frequency Characters I

Given a string s and an integer k, return the total number of

substrings

of s where at least one character appears at least k times.

Example 1:

Input: s = "abacb", k = 2

Output: 4

Explanation:

The valid substrings are:

• "aba" (character 'a' appears 2 times).
• "abac" (character 'a' appears 2 times).
• "abacb" (character 'a' appears 2 times).
• "bacb" (character 'b' appears 2 times).

Example 2:

Input: s = "abcde", k = 1

Output: 15

Explanation:

All substrings are valid because every character appears at least once.

Constraints:

• 1 <= s.length <= 3000
• 1 <= k <= s.length
• s consists only of lowercase English letters.

Solution:

class Solution {
    public int numberOfSubstrings(String s, int k) {
        int result = 0;
        // Map<Character, Integer> map = new HashMap<>();
        /*

        substrings of s 

        at least one character 

        abacb
        s
            f

        */

        if (k == 1){
            return (1 + s.length())*s.length()/2;
        }


        /*
                0 1 2 3 4
                a b a c b
                  i 
                    j
                <a, 2>
                <b, 1>



         */

        for (int i = 0; i < s.length() - 1; i++){
            char start = s.charAt(i); // a 
            Map<Character, Integer> map = new HashMap<>();
            map.put(start, map.getOrDefault(start, 0) + 1);
            for (int j = i + 1; j < s.length(); j++){
                char next = s.charAt(j); // b
                map.put(next, map.getOrDefault(next, 0) + 1);

                if (map.get(next) == k){ // 2
                    result = result + (s.length() - j);
                    // 0 + (5 - 2) = 0 + 3
                    break;
                }
            }
        }


        return result;
    }
}