Блог пользователя pkay_24

Help needed in this String problem
Автор pkay_24, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
← 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)$$$

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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<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$$$.

      → Ответить