# Longest Sub-string with at most K Distinct Characters

Posted: 11 Sep, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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.