Longest Substring with At Most K Distinct Characters

Moderate

0/80

Average time to solve is 20m

Contributed by

110 upvotes

Asked in companies

Problem statement

You are given a string 'str' and an integer ‘K’. Your task is to find the length of the largest substring with at most ‘K’ distinct characters.

For example:

You are given ‘str’ = ‘abbbbbbc’ and ‘K’ = 2, then the substrings that can be formed are [‘abbbbbb’, ‘bbbbbbc’]. Hence the answer is 7.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains one integer, ‘K’, representing the maximum number of unique characters allowed in the string.

The second line of each test case contains a single string ‘str’ representing the given string.

Output Format:

For each test case, print a single integer representing the length of largest substring that can be formed with at most ‘K’ unique characters.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
1 <= K <= 26
1 <= |str| <= 10^6

The string str will contain only lowercase alphabets.    

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Sample Input 1:

2
2
abbbbbbc
3
abcddefg

Sample Output 1:

7
4

Explanation:

For the first test case, ‘str’ = ‘abbbbbbc’ and ‘K’ = 2, then the substrings that can be formed are [‘abbbbbb’, ‘bbbbbbc’]. Hence the answer is 7.

For the second test case, ‘str’ = ‘abcddefg’ and ‘K’ = 3, then the substrings that can be formed is [‘cdde’, ‘ddef’]. Hence the answer is 4.

Sample Input 2:

2
3
aaaaaaaa
1
abcefg

Sample Output 2:

8   
1

Hints:

1. Try to think of a brute force approach.
2. Try to think of a two-pointer solution.

Console