3258. Count Substrings That Satisfy K-Constraint I

You are given a binary string s and an integer k.

A binary string satisfies the k-constraint if either of the following conditions holds:

• The number of 0‘s in the string is at most k.
• The number of 1‘s in the string is at most k.

Return an integer denoting the number of substrings of s that satisfy the k-constraint.

class Solution {
public:
    int countKConstraintSubstrings(string& s, int k) {
        deque<int> A{-1}, B{-1};
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '0') {
                A.push_back(i);
                while(A.size() - 1 > k) A.pop_front();
            }
            else {
                B.push_back(i);
                while(B.size() - 1 > k) B.pop_front();
            }
            res += i - min(A[0],B[0]);
        }
        return res;
    }
};