3325. Count Substrings With K-Frequency Characters I - Medium

前往題目

想法

• sliding window直接暴力解

思路

Weekly contest 420的題目

1. 左指針固定，右指針移動，每次都檢查當前字母數量是否大於等於k
2. 如果是的話更新結果，之後移動右指針也繼續結果+1，因為都還包含在內所以一定>=k
3. 右指針走到盡頭時，左指針往右移動一步，右指針重新初始化，重新一步一步展開window

Code

class Solution {
    public int numberOfSubstrings(String s, int k) {
        int l = 0, r = 0;
        int[] count = new int[26];
        Arrays.fill(count, 0);
        int res = 0;

        while (l < s.length() || r < s.length()) {
            char c = s.charAt(r);
            count[c - 97] += 1;

            // At least k times, so the following substrings will be all valid
            while (count[c - 97] >= k && r < s.length()) {
                ++res;
                ++r;
            }

            ++r;
            if (r >= s.length()) {
                // Reset left pointers to the next position
                ++l;
                r = l; // Reset right pointer
                // Reset the counts
                for (int i = 0; i < 26; ++i) {
                    count[i] = 0;
                }
            }
        }
        return res;
    }
}