Smirnoff24's blog

By Smirnoff24, history, 6 months ago, In English

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"
 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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<k$$$ so $$$freq$$$ decreases by $$$1$$$.
      • The fifth one is $$$021222$$$. $$$freq=0$$$

      $$$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$$$.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you provide a pseudocode for the approach you described?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

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

          #include<bits/stdc++.h>
          using namespace std;
          map<char,int> 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;i<n;i++){
                      mp[s[i]]++;
                      while(mp[s[i]]>k){
                          mp[start]--;
                          start++;
                      }
                      count+=fpos();
          
                  }
                  while(start<n){
                      mp[start]--;
                      count+=fpos();
                      start++;
                  }
                  return count;
              }
          }