Longest Substring with K Distinct Characters in Python 🐍 & CPP| Sliding Window Pattern | Coding Interview

When it comes to problems where subarray or substrings are inquired, their brute force approach is primarily similar (an O(n²), use two for loops to analyze each subarray). This problem is identical to Smallest Subarray with a Given Sum, and hence I should directly start with the attractive Sliding window solution.

This article belongs to the interview preparation plan, which you can find here.

Now let’s start with the our solution.

Description

We are given a string S and a number K, and we have to find the longest substring with at most K distinct characters.

Example 1:

Input: S = "ababcbcca", K = 2
Output: 5

Explanation: The longest substring with at most 2 distinct characters is "bcbcc" with characters 'b' and 'c'.

Example 2:

Input: S = abcde, K = 1
Output: 1

Explanation: Since all the characters of the strings are different, the substring length with K distinct characters depends on K itself.

Solution

Thinking of this problem, one might see that we are asking for a subarray holding some properties; in this case, it should have at most K distinct characters. These are kind of hints that should make you think of the sliding window pattern.

So we need a window that dynamically changes its size. It expands from the right side adding new elements and shrinks from the left side if the number of distinct characters increases K.

To maintain the number of distinct characters along with their frequency, we can use a hash table, where we add the new element to it while expanding the window and while shrinking the window, we can reduce the frequency of the character going out and if its frequency becomes zero we can remove the character from the hash table.

Whenever the window has at most K distinct characters, we can check if its size is the greatest we have seen and remember it.

If you are preparing for an interview, you might like these two articles:

So the algorithm for Longest Substring with K Distinct characters can be:

• Create a hash table to store a mapping between characters and their frequency.
• Insert new characters from the string until we have K distinct characters in the window. Remember the window size as the answer (longest we have seen so far).
• Then start expanding the window from the right or, in other words sliding the window by adding new elements.
• If at any time the number of distinct characters in the window reaches more than K, we will shrink the window from the right side and reduce the frequency of the character moving out until we have only K distinct characters.
• Whenever the character frequency in the hash table reaches 0, we will remove the character.
• After every expansion and shrinking, we will check if the current window has the largest size we have seen and if so, we will remember it.

An example will make things more clear, assume K = 2.

The following code is in python with proper comments. And, If you want c++, read here.

Code (Python)

Output:
5

Code (CPP)

Time & Space Complexity

Time: The outer for loop runs for n times, where n is the number of characters in the string and the inner while loop runs for each character only once hence the time complexity is linear or O(n).

Space: We are using a dictionary, which at any given time can have at most (K+1) keys; hence the space complexity is proportional to K, O(K).

Thank you for reading!

P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and helps all the writers.

If you liked what you just read, a clap would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn’t like it? Please do comment😋!

You can also follow me HERE to get updates on the stories that I write.