### Smirnoff24's blog

By Smirnoff24, history, 6 months ago,

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"

• +6

 » 6 months ago, # | ← Rev. 2 →   +6 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)$
•  » » 6 months ago, # ^ |   +3 Thanks for the answer. Could you possibly demonstrate the process with the mentioned test case ?
•  » » » 6 months ago, # ^ |   0 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. The first one is $110202$. Here all characters have frequency $k$, so $freq=3$. The second one is $102021$. $freq$ is still $3$. The third one is $020212$. $1$ and $2$ have frequencies different from $k$, so $freq$ decreases by $2$. The fourth one is $202122$. $0$ now has frequency \$1
•  » » » » 7 weeks ago, # ^ |   0 Could you provide a pseudocode for the approach you described?
•  » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Might have to fix few edge cases :), but this will do with O(n*alphabetsize) #include using namespace std; map mp; int fpos(){ bool possible = true; for(auto a:mp){ if(a.second!=k && a.second!=0) possible = false; } return possible; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--){ string s; cin>>s; int n = s.size(); mp.clear(); int start = 0; int64_t count = 0; for(int i=0;ik){ mp[start]--; start++; } count+=fpos(); } while(start