Sliding Window: Given a string a variable k, count substring with k frequency characters

Problem Statement:

You are given a string s, and k frequency.

You need to find the number of substrings that each character occurs at most k times.

Example:

Input: 

S = "abacb";
k = 2;

Output: 4

Solution Explanation:

Solution is very simple. We will use the frequency array.
Start from the index i and keep incrementing j one step at a time.
Then update the count of the char frequency.

When the frequency reaches the k, then update the answer and restart the substring calculation.

once a valid substring is found, then add all the substring starting at i and ending at j.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int solution(string s, int k) 
{
    int ans = 0;

    for (int i = 0; i < s.length(); i++) 
    {
        vector<int> freqArr(26, 0);

        for (int j = i; j < s.length(); j++) 
        {
            freqArr[s[j] - 'a']++;

            if (freqArr[s[j] - 'a'] == k) 
            {
                ans += s.length() - j;
                break;
            }
        }
    }

    return ans;
}


int main()
{
    string S = "abacb";
    int k = 2;
    cout << solution(S, k);
    return 0;
}

Output

4