Longest Sub-string with at most K Distinct Characters

Moderate
0/80
Average time to solve is 35m
33 upvotes
Asked in companies
SAP LabsHikeBNY Mellon

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Hint

Try to check every substring.

Approaches (4)
Brute Force
  • 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.
Time Complexity

O(N^3), where N is the size of the string.

 

We are generating all the substring in O(N^2) complexity and for every substring, one traversal will be required to check the number of distinct characters.

Space Complexity

O(1).

 

We are using constant extra space.

Code Solution
(100% EXP penalty)
Longest Sub-string with at most K Distinct Characters
Full screen
Console