class Solution {
    public int countKConstraintSubstrings(String S, int k) {
        char s[] = S.toCharArray();
        int[] cnt = new int[2];
        int sum = 0;
        int left = 0;
        for(int i = 0; i < s.length; i ++ )
        {
            cnt[s[i] & 1] ++ ;

            while(cnt[0] > k && cnt[1] > k)
            {
                cnt[s[left] & 1] -- ;
                left ++ ;
            }

            sum += i - left + 1;
        }

        return sum;
    }
}