Longest Substring with K Distinct Characters 🎯

Welcome to an exciting journey into the world of data structures and algorithms! Today, we'll explore a problem that requires us to find the longest substring in a given string with no more than K distinct characters. This problem is a fantastic way to understand and apply string manipulation, sliding window technique, and hash maps.

Understanding the Problem 📝

Given a string s and an integer k, return the length of the longest substring of s with no more than k distinct characters.

Examples

Let's consider some examples to better understand the problem:

s = "abcde", k = 2
- The longest substring with at most 2 distinct characters is "bc", which has a length of 3.
s = "abcde", k = 3
- The entire string "abcde" has 5 distinct characters, but the longest substring with at most 3 distinct characters is "abcde", which has a length of 4.

Solution Approach 💡

To solve this problem, we'll use a combination of the sliding window technique and a hash map (or a dictionary in some programming languages). Here's a high-level overview of our approach:

Initialize a hash map (countMap) and two pointers (start and end) to represent the window (substring) we're currently considering.
Iterate through the characters in the string s. For each character, add it to the window and update the count in the countMap.
While the number of distinct characters in the countMap exceeds k, keep moving the start pointer to the left, remove the character at start from the countMap, and decrease the size of the window.
Keep track of the maximum size of the window (substring) encountered during the iteration.
Once you've iterated through the entire string, return the maximum size of the window as the solution.

Now, let's dive into some code examples in Python to help you understand this approach better.

Python Code Example 📝

python

def longest_substring(s, k):
    countMap = {}
    start = 0
    max_length = 0

    for end in range(len(s)):
        if s[end] in countMap:
            countMap[s[end]] += 1
        else:
            countMap[s[end]] = 1

        while len(countMap) > k:
            countMap[s[start]] -= 1
            if countMap[s[start]] == 0:
                del countMap[s[start]]
            start += 1

        max_length = max(max_length, end - start + 1)

    return max_length

In this example, we first initialize an empty hash map and two pointers, start and end. We then iterate through the string s, updating the countMap and window size as we go. If we encounter a character that already exists in the countMap, we increment its count. If it's a new character, we add it to the countMap.

Next, we enter a loop where we maintain the number of distinct characters in the countMap. If the number of distinct characters exceeds k, we move the start pointer to the left, decrement the count of the character at start in the countMap, and remove it if its count becomes zero. We continue this loop until the number of distinct characters in the countMap is less than or equal to k.

Finally, we keep track of the maximum length of the window (substring) we've encountered during the iteration, and return this value as the solution.

Quiz 🎯

With this understanding of the Longest Substring with K Distinct Characters problem, you're well on your way to mastering important concepts in data structures and algorithms. Keep exploring and practicing, and you'll be solving complex problems in no time! 💪