Hello Community !!

So this question appeared in one of the interviews I had given.

Given a String s comprising of digits from 0-9. You need to count number of substrings such that each character present in that substring occurs exactly K times.

constraints: N = size of given string 1 <= N <= 10^5 1 <= K <= N

tc: s="1102021222" K=2 Ans=6

6 substrings are s[0:1]="11" , s[0:5]="110202" , s[1:6]="102021" , s[2:5]="0202" , s[7:8]="22" , s[8:9]="22"

For each number of distinct characters $$$d$$$ present in the substring you can do the following algorithm:

The length of the required substrings are $$$d \cdot k$$$. Calculate the number of frequencies equal to $$$k$$$ from the first $$$d \cdot k$$$ characaters. After that move the substring by one position. The count of frequencies can change from removing the first character or adding the last one (or possibly both). Repeat this until you reach the final substring.

Time complexity: $$$O(N \cdot alphabetSize)$$$, which is in this case $$$O(N \cdot 10)$$$

Thanks for the answer. Could you possibly demonstrate the process with the mentioned test case ?

Let $$$freq$$$ be the number of frequencies equal to $$$k$$$.

So for example let's consider all of the substrings consisting of $$$3 \cdot k$$$ characters.

$$$freq$$$ is equal to the number of distinct characters ($$$3$$$) only in the first two substrings, so we add $$$2$$$ to the total count. Apply the same algorithm for the substrings of length $$$1 \cdot k$$$ and $$$2 \cdot k$$$.

Could you provide a pseudocode for the approach you described?

Might have to fix few edge cases :), but this will do with O(n*alphabetsize)