The longest substring in it with no more than K distinct characters

Today we shall a sliding window pattern question.

How to the length of the longest substring in it with no more than K distinct characters ?

The first and foremost step to solve the problem is to understand the question and figure what is given and what are we supposed to return as a result.

In this problem, we are given a string say str and an integer k . We are asked to return an integer say max_size which is the length of the longest sub string with less than the "k" number of distinct characters. Let's see the examples.

Example 1:

Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

Example 2:

Input: String="araaci", K=1
Output: 2
Explanation: The longest substring with no more than '1' distinct characters is "aa".

Example 3:

Input: String="cbbebi", K=3
Output: 5
Explanation: The longest substrings with no more than '3' distinct characters are "cbbeb" & "bbebi".

Example 4:

Input: String="cbbebi", K=10
Output: 6
Explanation: The longest substring with no more than '10' distinct characters is "cbbebi".

With this we have finally understood the question, So let's get started on thinking about how to solve the question

We can use a sliding window pattern

We'll start by inserting characters from the beginning of the string until the HashMap has K distinct characters.
Our sliding window will be formed by these characters. We're supposed to discover the window with the fewest number of unique characters. The length of this window will be remembered as the longest thus far.
Following that, we'll incrementally add one character to the sliding window (i.e., slide the window forward).
If the number of different characters in the HashMap is more than K, we'll try to reduce the window from the beginning of each phase. We'll reduce the size of the window until the HashMap contains no more than K unique characters.

Let's get to the code !

def Longest_Substring_with_K_Distinct_Characters(string, k):
    max_size = 0
    window_start = 0
    hashmap = {}
    for window_end in range(len(string)):
        right_char = string[window_end]
        if right_char not in hashmap:
            hashmap[right_char] = 0
        hashmap[right_char] += 1

        while len(hashmap) > k:
            hashmap[string[window_start]] -= 1
            if hashmap[string[window_start]] == 0:
                del hashmap[string[window_start]]

            window_start += 1
            max_size = max(max_size, window_end - window_start + 1)
    return max_size


string = "araaci"
k = 2

print(Longest_Substring_with_K_Distinct_Characters(string, k))

Happy coding 🙌🙌✌️👋👋

How to find the length of the longest substring in it with no more than K distinct characters ?

Comments

More from this blog

Dutch National Flag problem

How to find the number of islands in a matrix

How to enable Multi-Factor Authentication (MFA) for S3 buckets?

How to Deploy the static website to S3 using GitHub actions.

Command Palette

Comments

More from this blog