Problem title
Difficulty
Avg time to solve

Relative Sorting
Moderate
25 mins
Permutations of a String
Moderate
15 mins
Maximum of All Subarrays of Size K
Easy
15 mins
0 1 Knapsack
Moderate
--
Flood Fill Algorithm
Moderate
10 mins
Common Elements In Three Sorted Arrays
Moderate
35 mins
Job Sequencing Problem
Moderate
30 mins
Number Pattern
Easy
10 mins
BST to sorted DLL
Moderate
50 mins
Minimum Cost To Connect Two Groups Of Points
Hard
15 mins
17

Longest Sub-string with at most K Distinct Characters

Difficulty: MEDIUM
Contributed By
Avg. time to solve
35 min
Success Rate
65%

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
Sample Input 1:
2
2
abcba
1
abccc
Sample Output 1:
3
3
Explanation of the Sample Input1:
Test Case 1:
K = 2 in the first test case so we can choose substring ‘bcb’ having 2 distinct characters which are less than equal to K=2. 
We cannot get any other substring of length 4 or greater having distinct characters less than equal to 2.
Test Case 2:
K = 1 in the second test case so we can choose substring ‘ccc’ having only 1 distinct character which is less than equal to K=1. 
We cannot get any other substring of length 4 or greater having distinct characters less than equal to 1.
Reset Code
Full screen
copy-code
Console