Number of substrings with count of each character as k

#1

Could you suggest a better approach for this problem ?

#2

Hey @nidhigupta847
This cant be solved in O(n)

But let me give you one optmization in the given solution .
take a matrix of nx26 where n is length of string
and do

for(int i=0;i<n;i++){
     mat[i][s[i]-'a']++;
    if(i==0) continue;
     for(int j=0;j<26;j++){
         mat[i][j]+=mat[i-1][j];
     }
}

This precomputes the count of characters from 0 to ith index.

2nd optimization
Now u Only have to check strings of length which are multiple of k
so do

for(int i=k;i<n;i=i+k){
    for(int j=0;j+i<n;j++){
         \\Here check if all the letters count are multiples of k or not using precomputed matrix 
         \\operation complexity is O(26)==O(1)
    }
}

So the complexity of above program becomes
n/k+n/2k+n/3k+…n/n
I am not going into mathematics but it surely is less than n^2 in an average case

#3

can you paste complete code