Ninja and Repeating Substring

Moderate
0/80
Average time to solve is 30m
1 upvote
Asked in company
Microsoft

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
9 2
abcbacadc
6 3
ababbbc
Sample Output 1:
7
3
Explanation of sample input 1:
For the first test case,

The longest substring satisfying the given condition is “abcbaca” as the frequency of ‘a’ is 3, frequency of ‘b’ is 2, and frequency of ‘c’ is 2. All these frequencies are greater than or equal to 2. Hence, the answer is 7 corresponding to the length of the substring.


For the second test case:

The longest substring satisfying the given condition is “bbb” as the frequency of ‘b’ is 3, which is greater than or equal to k. Hence, the answer is 3 corresponding to the length of the substring.
Sample Input 2:
2
7 3
abcebbc
8 3
daedddee
Sample Output 2:
0
6
Hint

Check for each substring.

Approaches (2)
Brute Force

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’.
Time Complexity

O(N^2), where ‘N’ is the number of characters in string ‘S’.

 

In this approach, we are checking each substring and for each substring, we are traversing the ‘FREQ’ to check the frequency of each letter. So the total time will be O(26*N*N). Hence,the overall time complexity will be O(N^2).

Space Complexity

In this approach, we are an array of size 26 to store the frequency of each letter. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja and Repeating Substring
Full screen
Console