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

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

Sliding Window

Muthya Varshith Vankamamidi's photo
Muthya Varshith Vankamamidi
ยทAug 22, 2021ยท

2 min read

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.

Array.png

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 ๐Ÿ™Œ๐Ÿ™ŒโœŒ๏ธ๐Ÿ‘‹๐Ÿ‘‹

Did you find this article valuable?

Support Muthya Varshith Vankamamidi by becoming a sponsor. Any amount is appreciated!

See recent sponsors |ย Learn more about Hashnode Sponsors
ย 
Share this