Last Updated: 13 Dec, 2021

Ninja and Repeating Substring

Moderate

Asked in company

Solve now

Problem statement

Ninja is playing with a string ‘S’ consisting of ‘N’ lowercase letters. Ninja is observing the string carefully, he wants to know if any substring of ‘S’ has that the frequency of each character in this substring is greater than or equal to ‘K’.Ninja is not concerned about the string but wants to the length of the longest substring which satisfies the given condition.

You are given a string ‘S’ having ‘N’ lowercase letters. Your task is to print the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

For Example

If the given string S = “abcbacadc” and k = 2.The answer will be 7 corresponding to the length of the substring “abcbaca” as the frequency of characters‘ a’ , ‘b’ and ‘c’, all are greater than or equal to 2.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, ‘N’ denoting the number of characters present in string S and ‘K’.

The following line contains the string ‘S’.

Output Format:

For each test case, print ‘an integer corresponding to the minimum number of swaps required.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^6.
1 <= K <= 1000.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will declare an array of size 26 to store the frequency of each letter. We will just try for all possible substrings and check if the substring satisfies the given conditions or not. If it satisfies the condition, we will update the ‘ANS’.

Algorithm:

Declare an array ‘FREQ’ of size 26 to store the frequency of each letter.
Declare an integer ‘ANS’ to store the length of the longest substring.
Set ‘ANS’ as 0.
For i in range 0 to N-1:
- Set all values of ‘FREQ’ to 0.
- For j in range i to N-1:
  - Set FREQ[S[j]] as FREQ[S[j]] + 1.
  - Set ‘IS_GOOD’ as TRUE.
  - For c in range 0 to 25:
    - If FREQ[c] > 0 && FREQ[c]< ‘K’:
      - Set IS_GOOD as False.
      - Break.
  - If IS_GOOD is true:
    - Set ‘ANS’ as the maximum of ‘ANS’ and (j-i+1).
Return ’ANS’.

Solve now

02 Approach

In this approach, we will first decide that we are checking for how many unique characters are in our substring. We will try all numbers from 1 to 26. Then, we will iterate through the string with two pointers

we will declare two pointers ‘i’ and ‘j’ to traverse the string. ‘i‘ and ‘j’ both will be pointing to the first character. We will count ‘UNIQUE’ that will count the number of uniques in the current substring and ‘AT_LEAST_K’ to store the number of characters having a frequency greater than K.

While j is less than N:

If UNIQUE is less than the fixed Unique:

We will add a character to the window and set j as j +1.

Else:

We will remove a character from the window and set i as i +1.

After this, we will update the ‘FREQ’ array and ‘UNIQUE’ and ‘AT_LEAST_K’ count.

If UNIQUE count is equal to fixed unique count and UNIQUE count is equal to ‘AT_LEAST_K’.We found a suitable substring. Update ‘ANS’.

At last, we will return ‘ANS’ storing the length of the longest substring.

Algorithm:

Declare an array ‘FREQ’ of size 26 to store the frequency of each letter.
Declare an integer ‘ANS’ to store the length of the longest substring.
Set ‘ANS’ as 0.
For ‘FIXED_UNIQUE’ in range 1 to 26:
- Set all values of ‘FREQ’ to 0.
- Set ‘UNIQUE’ as 0.
- Set ‘At_LEAST_K’ as 0.
- Set i as 0.
- Set j as 0.
- While j < N:
  - If ‘ UNIQUE’ <= ‘FIXED_UNIQUE’:
    - Set FREQ[S[j]] to FREQ[S[j]] + 1.
    - If FREQ[S[j]] is equal to 1:
      - Set ‘UNIQUE’ as UNIQUE + 1.
    - If FREQ[S[j]] is equal to ‘K’:
      - Set ‘AT_LEAST_K’ as ‘AT_LEAST_K’ + 1.
    - Set j to j+1.
  - Else:
    - Set FREQ[ S[i] ] to FREQ[ S[i]] - 1.
    - If FREQ[S[i]] is equal to 0:
      - Set ‘UNIQUE’ as UNIQUE - 1.
    - If FREQ[S[j]] is equal to ‘K-1’:
      - Set ‘AT_LEAST_K’ as ‘AT_LEAST_K’ - 1.
    - Set i to i+1.
  - If ‘UNIQUE’ is equal to FIXED_UNIQUE and UNIQUE is equal to AT_LEAST_K:
    - Suitable substring found.
    - Set ‘ANS’ as the maximum of ‘ANS’ and (j-i).
Return ‘ANS’.

Solve now