Longest Sub-string with at most K Distinct Characters

Posted: 11 Sep, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given string S of length N, and an integer K. Your task is to find the length of the longest substring that contains at most K distinct characters.

Input Format:
The first line contains an Integer 'T' which denotes the number of test cases/queries to be run. 
Then the test cases follow. 

The first line of input for each test case/query contains an integer K.

The second line of input for each test case/query contains a string S.
Output Format:
For each test case, print the length of the longest substring that contains at most K distinct characters.

Output for every test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= K <= 26
1 <= N <= 10^4

Time Limit: 1sec
Approach 1
  • We will generate all the substrings using 2 nested for loops and we will have a ‘CHECK’ function which returns true if the number of distinct character in the substring is less than equal to K otherwise false.
  • We will have an ans variable initialize to 0. We will call the ‘CHECK’ function with every substring and if it returns true then
    • ANS = MAX(ANS , CURRENT_SUBSTRING.SIZE())
  • To implement the check function we will have K and substring S as inputs and we will create an array of size 26 let’s call this ‘FREQ’ and initialize all position with 0.
    • Increase the frequency of every character in the substring S.
      • FREQ[S[i]-’a’]++
    • Have a variable ‘DISTINCT’ = 0
      • Then run a loop from i = 0 to i = 25 and increase the ‘DISTINCT’ if FREQ[i] is non-zero.
    • Return true if DISTINCT <= K otherwise return false
  • Finally, return ANS which have our required answer.
Try Problem