Longest Sub-string With K Distinct Characters
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.

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

Question

Longest Sub-string With K Distinct Characters

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.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

We are using ‘freq’ array/list of size 26 to store the count of characters. Thus, the space complexity is constant.

Time Complexity: O(n^3)Explanation:

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.

Java (SE 1.8)

/*

    Time Complexity : O(N ^ 3)

    Space Complexity : O(1)



    Where N is the size of the string.

*/



public class Solution {



    // Use it to check if the string 's' has at most 'k' distinct characters.

    public static boolean check(String s, int k) {

        int freq[] = new int[26];



        for (int i = 0; i < s.length(); i++) {

            freq[s.charAt(i) - 'a']++;

        }



        int distinct = 0;



        for (int i = 0; i < 26; i++) {

            // Increase the count of distinct characters.

            if (freq[i] > 0) {

                distinct++;

            }

        }



        return distinct <= k;

    }



    public static int getLengthofLongestSubstring(String s, int k) {

        int longestLength = 0;

        int n = s.length();



        for (int i = 0; i < n; i++) {

            String current = "";



            for (int j = i; j < n; j++) {

                current += s.charAt(j);



                // Check if the substring from '[i, j]' has at most 'k' distinct characters.

                if (check(current, k)) {

                    // Update 'longestLength' accordingly.

                    longestLength = Math.max(longestLength, j - i + 1);

                }

            }

        }



        return longestLength;

    }

}

Accepted Answer

Improved Version

We will run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’ where ‘i’ will be the starting position of the substring and ‘j = i’ to ‘j = N - 1’ where ‘j’ will be the end position of the substring.
Before starting the second loop, we will create a hash table or an array/list of size 26. Let’s call this array ‘freq’.
Inside the inner loop increase the frequency of the ‘j-th’ character.
Now, 'freq' array will have the frequency of the substring starting from the index ‘i’ and ending at the index ‘j’.
- We will check the number of distinct characters, which will be the number of the non-zero valued position in the 'freq' array.
Initialize a variable ‘longestLength = 0’, and if the number of distinct characters is less than equal to ‘K’, then:
- ‘longestLength = max(longestLength, j - i + 1)’
Return ‘longestLength’, which is the required answer.

Space Complexity: O(1)Explanation:

O(1).

We are using ‘freq’ array/list of size 26 to store the count of characters. Thus, the space complexity is constant.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of the string.

We are generating the frequency array for all the substrings using two nested for loops only.

Python (3.5)

'''

    Time Complexity : O(N ^ 2)

    Space Complexity : O(1)



    Where N is the size of the string.   

'''



# Returns the number of distinct characters in the list 'freq'.

def countDistinct(freq):

    distinct = 0



    for i in range(26):

        if freq[i] > 0:

            distinct += 1



    return distinct



def getLengthofLongestSubstring(s, k):



    longestLength = 0

    n = len(s)



    for i in range(n):

        freq = [0] * 26



        for j in range(i, n):

            freq[ord(s[j]) - ord('a')] += 1

            # Check if 'freq' contains at most 'k' distinct characters.

            if countDistinct(freq) <= k:

                # Update 'longestLength' accordingly.

                longestLength = max(longestLength, j - i + 1)



    return longestLength

Java (SE 1.8)

/*

    Time Complexity : O(N ^ 2)

    Space Complexity : O(1)



    Where N is the size of the string.

*/



public class Solution {



    // Returns the number of distinct characters in the array 'freq'.

    public static int countDistinct(int[] freq) {

        int distinct = 0;



        for (int i = 0; i < 26; i++) {

            if (freq[i] > 0) {

                distinct++;

            }

        }



        return distinct;

    }



    public static int getLengthofLongestSubstring(String s, int k) {

        int longestLength = 0;

        int n = s.length();



        for (int i = 0; i < n; i++) {

            int freq[] = new int[26];



            for (int j = i; j < n; j++) {

                freq[s.charAt(j) - 'a']++;



                // Check if 'freq' contains at most 'k' distinct characters.

                if (countDistinct(freq) <= k) {

                    // Update 'longestLength' accordingly.

                    longestLength = Math.max(longestLength, j - i + 1);

                }

            }

        }



        return longestLength;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N ^ 2)

    Space Complexity : O(1)



    Where N is the size of the string.

*/



#include 



// Returns the number of distinct characters in the array 'freq'.

int countDistinct(vector &freq) {

    int distinct = 0;



    for (int i = 0; i < 26; i++) {

        if (freq[i]) {

            distinct++;

        }

    }



    return distinct;

}



int getLengthofLongestSubstring(string s, int k) {

    int longestLength = 0;

    int n = s.size();



    for (int i = 0; i < n; i++) {

        vector freq(26, 0);



        for (int j = i; j < n; j++) {

            freq[s[j] - 'a']++;



            // Check if 'freq' contains at most 'k' distinct characters.

            if (countDistinct(freq) <= k) {

                // Update 'longestLength' accordingly.

                longestLength = max(longestLength, j - i + 1);

            }

        }

    }



    return longestLength;

}

Accepted Answer

Using Binary Search

We will be doing the binary search on the answer that is the length of the substring.
- ‘low = 1’ and ‘high = N’ will be the range of our answer. We will have a variable ‘longestLength = 0’ to store the required answer.
Now, we will loop till ‘low <= high’, and we will find the ‘mid’.
- We will try to find if there is a substring of length equal to ‘mid’, which has distinct characters less than equal to ‘K’.
- To check the number of distinct characters in a substring of length equal to 'mid', we will use the sliding window with a hash table or an array/list of size 26.
- If it is possible to find such substring with length ‘mid’, then we can try for a bigger length substring, so:
  - ‘low = mid + 1’
  - ‘longestLength = max(longestLength, mid)’
- Otherwise, we need to decrease the substring size, so
  - ‘high = mid - 1’

Now, after the binary search, we will have our required answer in the variable ‘longestLength’.

Space Complexity: O(1)Explanation:

O(1).

We are using ‘freq’ array/list of size 26 to store the count of characters. Thus, the space complexity is constant.

Time Complexity: O(nlogn)Explanation:

O(N * logN), where ‘N’ is the size of the string.

We are performing the binary search on the length which gives ‘O(logN)’ time complexity and for each iteration, we will be traversing the whole string which will take ‘O(N)’ time complexity.

Python (3.5)

'''

    Time Complexity : O(N * logN)

    Space Complexity : O(1)



    Where N is the size of the string.  

'''



# Returns the number of distinct characters in the list 'freq'.

def countDistinct(freq):

    distinct = 0



    for i in range(26):

        if freq[i] > 0:

            distinct += 1



    return distinct



def getLengthofLongestSubstring(s, k):



    longestLength = 0

    n = len(s)

    low, high = 1, n



    while low <= high:



        mid = low + (high - low) // 2

        possible = False

        freq = [0] * 26



        for i in range(mid):

            freq[ord(s[i]) - ord('a')] += 1



        possible |= (countDistinct(freq) <= k)

        

        # Using sliding window, check if a valid substring of length 'mid' is possible.

        for i in range(mid, n):

            freq[ord(s[i]) - ord('a')] += 1

            freq[ord(s[i - mid]) - ord('a')] -= 1

            possible |= (countDistinct(freq) <= k)



        '''

            If a valid substring of length 'mid' is possible then update 'longestLength'

            and check for substrings having length greater than 'mid'.

        '''

        if possible:

            longestLength = max(mid, longestLength)

            low = mid+1

        # If no such substring is possible check for substrings with length less than 'mid'.

        else:

            high = mid-1



    return longestLength

C++ (g++ 5.4)

/*

    Time Complexity : O(N * logN)

    Space Complexity : O(1)



    Where N is the size of the string.

*/



#include 



// Returns the number of distinct characters in the array 'freq'.

int countDistinct(vector& freq) {

    int distinct = 0;



    for (int i = 0; i < 26; i++) {

        if (freq[i]) {

            distinct++;

        }

    }



    return distinct;

}



int getLengthofLongestSubstring(string s, int k) {

    int longestLength = 0;

    int n = s.size();



    int low = 1, high = n;



    while (low <= high) {

        int mid = low + (high - low) / 2;

        bool possible = false;

        vector freq(26, 0);



        for (int i = 0; i < mid; i++) {

            freq[s[i] - 'a']++;

        }



        possible |= (countDistinct(freq) <= k);



        // Using sliding window, check if a valid substring of length 'mid' is possible.

        for (int i = mid; i < n; i++) {

            freq[s[i] - 'a']++;

            freq[s[i - mid] - 'a']--;

            possible |= (countDistinct(freq) <= k);

        }



        /*

            If a valid substring of length 'mid' is possible then update 'longestLength'

            and check for substrings having length greater than 'mid'.

        */

        if (possible) {

            longestLength = max(longestLength, mid);

            low = mid + 1;

        }

        // If no such substring is possible check for substrings with length less than 'mid'.

        else {

            high = mid - 1;

        }

    }



    return longestLength;

}

Java (SE 1.8)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(1)



    Where N is the size of the string.

*/



public class Solution {



    // Returns the number of distinct characters in the array 'freq'.

    public static int countDistinct(int[] freq) {

        int distinct = 0;



        for (int i = 0; i < 26; i++) {

            if (freq[i] > 0) {

                distinct++;

            }

        }



        return distinct;

    }



    public static int getLengthofLongestSubstring(String s, int k) {

        int longestLength = 0;

        int n = s.length();



        int low = 1, high = n;



        while (low <= high) {

            int mid = low + (high - low) / 2;

            boolean possible = false;

            int freq[] = new int[26];



            for (int i = 0; i < mid; i++) {

                freq[s.charAt(i) - 'a']++;

            }



            possible |= (countDistinct(freq) <= k);



            // Using sliding window, check if a valid substring of length 'mid' is possible.

            for (int i = mid; i < n; i++) {

                freq[s.charAt(i) - 'a']++;

                freq[s.charAt(i - mid) - 'a']--;

                possible |= (countDistinct(freq) <= k);

            }



            /*

                If a valid substring of length 'mid' is possible then update 'longestLength'

                and check for substrings having length greater than 'mid'.

            */

            if (possible) {

                longestLength = Math.max(longestLength, mid);

                low = mid + 1;

            }



            // If no such substring is possible check for substrings with length less than 'mid'.

            else {

                high = mid - 1;

            }

        }



        return longestLength;

    }

}

Accepted Answer

Optimal Approach

Create a hash table or a frequency array, and let's name it ‘freq’ and initialize all the positions with 0.
We will have a variable ‘start = 0’, which will be the left boundary of the sliding window.
We will run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’, which will be the right boundary of the sliding window.
- Increase the frequency of ‘i-th’ character i.e ‘freq[S[i] - ‘a’]++’.
- Now, we need to ensure that the substring has less than or equal to ‘K’ distinct characters.
  - So we will run a loop and check if the ‘freq’ array has greater than ‘K’ distinct characters. If it has greater than ‘K’ distinct characters we do ‘freq[S[start] - ’a’]--’.
- Once we come out of the loop, our current window (bounded by index ‘start’ and ‘i’) has less than or equal to ‘K’ distinct characters.
- We will maintain the variable ‘longestLength’, which will be our required answer.
We have our required answer in ‘longestLength’, so we return it.

Space Complexity: O(1)Explanation:

O(1).

We are using ‘freq’ array/list of size 26 to store the count of characters. Thus, the space complexity is constant.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the string.

We will be visiting every character at max twice. Thus, the time complexity is ‘O(N)’.

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(1)



    Where N is the size of the string.   

'''



# Returns the number of distinct characters in the list 'freq'.

def countDistinct(freq):

    distinct = 0



    for i in range(26):

        if freq[i] > 0:

            distinct += 1



    return distinct



def getLengthofLongestSubstring(s, k):



    longestLength = 0

    n = len(s)



    freq = [0] * 26

    

    # Starting index of the window

    start = 0



    # Traverse for ending index of the window

    for i in range(n):

        

        freq[ord(s[i])-ord('a')]+=1



        while countDistinct(freq) > k:

            freq[ord(s[start]) - ord('a')] -= 1

            start+=1



        longestLength = max(longestLength, i - start + 1)



    return longestLength

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    Where N is the size of the string.

*/



public class Solution {



    // Returns the number of distinct characters in the array 'freq'.

    public static int countDistinct(int[] freq) {

        int distinct = 0;



        for (int i = 0; i < 26; i++) {

            if (freq[i] > 0) {

                distinct++;

            }

        }



        return distinct;

    }



    public static int getLengthofLongestSubstring(String s, int k) {



        int longestLength = 0;

        int n = s.length();



        int freq[] = new int[26];



        // Starting index of the window.

        int start = 0;



        // Traverse for ending index of the window.

        for (int i = 0; i < n; i++) {

            freq[s.charAt(i) - 'a']++;



            while (countDistinct(freq) > k) {

                freq[s.charAt(start) - 'a']--;

                start++;

            }



            longestLength = Math.max(longestLength, i - start + 1);

        }



        return longestLength;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    Where N is the size of the string.

*/



#include 



// Returns the number of distinct characters in the array 'freq'.

int countDistinct(vector& freq) {

    int distinct = 0;



    for (int i = 0; i < 26; i++) {

        if (freq[i]) {

            distinct++;

        }

    }



    return distinct;

}



int getLengthofLongestSubstring(string s, int k) {

    int longestLength = 0;

    int n = s.size();



    vector freq(26, 0);



    // Starting index of the window.

    int start = 0;



    // Traverse for ending index of the window.

    for (int i = 0; i < n; i++) {

        freq[s[i] - 'a']++;



        while (countDistinct(freq) > k) {

            freq[s[start] - 'a']--;

            start++;

        }



        longestLength = max(longestLength, i - start + 1);

    }



    return longestLength;

}

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:

Input Format:

Output Format:

Note:

Constraints:

Top Lifesight Software Developer interview questions & answers

Popular interview questions of Software Developer