K Characters Substring

Moderate
0/80
profile
Contributed by
1 upvote
Asked in company
Amazon

Problem statement

You are given a string ‘str’, and an integer ‘K’, your task is to find the length of the longest substring such that the frequency of each character is greater than or equal to ‘K’.

For example: 
You are given, ‘str’ = ‘aabba’, and ‘K’ = 2, The longest substring with each character’s frequency at least ‘K’ is ‘aabba’, whose length is 5. Hence the answer is 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘K’ representing the integer given.

The second line of each test case contains the string ‘str’ representing the given string.
Output Format: 
For each test case print a single integer representing the longest substring with the frequency of each character at least K.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= K <= 10^5
1 <= |str| <= 10^4

Time Limit: 1 sec
Sample Input 1:
2
2
aabba
3
aabaabbc
Sample Output 1:
5
7
Explanation:
For the first test case, ‘str’ = ‘aabba’, and ‘K’ = 2, The longest substring with each character’s frequency at least ‘K’ is ‘aabba’, whose length is 5. Hence the answer is 5.

For the second test case, ‘str’ = ‘ aabaabbc’, and ‘K’ = 3. The longest substring with each character’s frequency at least ‘K’ is ‘aabaabb’, whose length is 7. Hence the answer is 7.
Sample Input 2:
2
2
abcab
1
abced
Sample Output 2:
0
5
Hint

Try to consider all the substrings

Approaches (3)
Brute Force

In this approach, we can traverse over every substring of the given string and check if all of its characters have a minimum frequency of ‘K’.

If a substring has all characters with a minimum frequency of ‘K’ we try to update our solution with its length.

 

We will create an isStringValid(subStr, k) method, that checks if the ‘subStr’ has all characters with a minimum frequency of k.

 

Algorithm:

  • In the isStringValid(subStr, k) method
    • Create array freq, and store the frequency of each character in the string ‘subStr’ in freq map.
    • Iterate key over freq
      • If freq[key] is less than K return False
    • At the end of the function return True.
  • In the given function
    • Set ans as 0
    • Iterate i from 0 to the length of the string
      • Iterate j from i + 1 to the length of the string
        • If isStringValid(substring of string from i to j, k) is True
          • Set ans as the maximum of itself and length of the substring of string from i to j.
    • Return ans
Time Complexity

O(N^3), Where N is the length of the string

 

We are iterating over all the substrings of the given string, which costs O(N^2) and for each substring, we are checking if it's valid or not hence the overall time complexity is O(N^2)*O(N) = O(N^3).

Space Complexity

O(1),

 

We are maintaining a frequency counter of each substring but it will only have 26 elements. Hence the total space complexity is O(1).

Code Solution
(100% EXP penalty)
K Characters Substring
Full screen
Console