pkay_24's blog

Help needed in this String problem
By pkay_24, history, 4 years 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

Comments Comments (3)
| Write comment?
»
4 years 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)$$$

→ Reply
  • »
    »
    4 years 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 ?

    → Reply
    • »
      »
      »
      4 years 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$$$.

      → Reply