3325.count-substrings-with-k-frequency-characters-i.md

3325. Count Substrings With K-Frequency Characters I

Sliding Window

• Window: the substrings that contain at least k frequency characters.
• We expand the window until it satisfies the condition (there are at least one k frequency characters in the window).
• We shrink the window until it breaks the condition.

k = 2

// At the beginning:
[i, j, k, a, b, a, ...]
 L 
 R ->

// Try to expand the window until it meets the condition:
[i, j, k, a, b, a, ...]
          ^^^^^^^
 L ->
                R // count['a'] = 2, meets the condition

// Start to shrink the window until it breaks the condition:
[i, j, k, a, b, a, ...]
          ^^^^^^^
          -> L
                R // count['a'] = 1, breaks the condition

// All the substrings from s[0:R] to s[L-1:R] meet the condition, total is L.
          a, b, a
       k, a, b, a
    j, k, a, b, a
 i, j, k, a, b, a

fun numberOfSubstrings(s: String, k: Int): Int {
    var ans = 0
    var left = 0
    var right = 0
    val count = IntArray(26)
    // Try to expand the window until it meets the condition:
    for (right in 0 until s.length) {
        count[s[right] - 'a']++

        // Start to shrink the window until it breaks the condition:
        while (count[s[right] - 'a'] >= k) {
            // Or equivalently, the number of subarray is lenght of string - remaining elements after right pointer.
            // ans += (s.length - right)
            count[s[left] - 'a']--
            left++
        }
        // All the substrings from s[0:R] to s[L-1:R] meet the condition, total is L.
        ans += left
    }
    return ans
}