Longest Sub-string With K Distinct Characters

Easy
0/40
Average time to solve is 15m
profile
Contributed by
85 upvotes
Asked in companies
AmazonCodenationLifesight

Problem statement

You are given a string 'S' of length 'N' consisting of lowercase English alphabet letters. You are also given a positive integer 'K'.

Now, a substring of this string is good if it contains at most 'K' distinct characters. A string 'X' is a substring of string 'Y' if it can be obtained by deletion of several continuous elements(possibly zero) from the beginning and the end from the string 'Y'.

Your task is to return the maximum size of any good substring of the string 'S'.

Example: 
‘S’ = “bacda” and ‘K’ = 3.

So, the substrings having at most ‘3’ distinct characters are called good substrings. Some possible good substrings are:
1. “bac”
2. “acd”
3. “acda”

The substring “acda” is the largest possible good substring, as we cannot get any other substring of length 5 or more having distinct characters less than or equal to ‘3’. Thus, you should return ‘4’ as the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains a single integer ‘K’, denoting the maximum number of distinct characters.

The second line of each test case contains a string ‘S’
Output Format: 
For each test case, print a single line containing an integer denoting the length of the longest substring that contains at most 'K' distinct characters.

The output of each 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 given function.
Constraints: 
1 <= T <= 10
1 <= K <= 26
1 <= N <= 10^4

All the characters of the string are lowercase English alphabet letters.

Time Limit: 1 sec
Sample Input 1:
2
2
abcbc
1
abccc
Sample Output 1:
4
3
Explanation For Sample Input 1:
For the first test case :
K = 2, so we can choose substring “bcbc” having 2 distinct character which is less than or equal to K = 2. 

We cannot get any other substring of length 5 or more having distinct characters less than or equal to 2. Thus, you should return ‘4’ as the answer.

For the second test case :
K = 1, so we can choose substring “ccc” having only 1 distinct character which is less than or equal to K = 1. 

We cannot get any other substring of length 4 or more having distinct characters less than or equal to 1. Thus, you should return ‘3’ as the answer.
Sample Input 2:
1
6
abcba
3
acbdab
Sample Output 2:
5
4
Hint

Try to check every substring.

Approaches (4)
Brute Force
  • We will generate all the substrings using two nested loops and have a ‘check’ function which returns ‘true’ if the number of distinct characters in the substring is less than equal to K, otherwise ‘false’.
  • We will have a ‘longestLength’ variable initialized to 0. We will call the ‘check’ function with every substring, and if it returns true, then:
    • ‘longestLength = max(longestLength, currentSubstring.size())’
  • To implement the ‘check’ function, we will create a frequency array of size 26 ‘freq’ with each element initialized to zero.
    • Increase the frequency of every character in the substring S.
      • ‘freq[S[i] - ’a’]++’
    • Have a variable ‘distinct = 0’.
      • Then run a loop where ‘i’ ranges from ‘0’ to ‘25’ and increase the ‘distinct’ if freq[i] is non-zero.
    • Return ‘true’ if ‘distinct <= K’. Otherwise, return ‘false’.

Finally, return ‘longestLength’, which has 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 ‘freq’ array/list of size 26 to store the count of characters. Thus, the space complexity is constant.

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