Leetcode 340 - Longest Substring with At Most K Distinct Characters

Understanding the problem

Given a string s and an integer k, find the length of the longest substring T that contains at most k distinct characters.

In the problem “Longest Substring with At Most K Distinct Characters”, we are given a string s and an integer k. The task is to find the length of the longest substring T of the given string s such that T contains at most k distinct characters.

For example, consider the string “eceba” and k = 2, the longest substring T that contains at most 2 distinct characters is “ece” which has a length of 3.

It’s important to note that the substring T can have repeating characters, for example, consider the string “aa” and k = 1, the longest substring T that contains at most 1 distinct character is “aa” which has a length of 2.

The main objective of this problem is to find the longest substring with at most k distinct characters from the given string s, which can be achieved by using the sliding window approach to keep track of the distinct characters in the current window and updating the maximum length of the substring seen so far.

Plan your solution

We can use the sliding window approach to solve this problem. First, we will initialize a left and right pointer to the start of the string. Then, we will iterate through the string with the right pointer, adding each character to a set to keep track of the distinct characters in the current window. If the size of the set exceeds k, we will remove the leftmost character of the window by incrementing the left pointer. We will keep track of the maximum length of the substring seen so far and return the result after the iteration.

Implement your solution

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    left = 0  # Initialize the left pointer of the window
    max_len = 0  # Initialize a variable to store the maximum length of the substring seen so far
    char_set = set()  # Initialize a set to keep track of the distinct characters in the current window
    for right in range(len(s)):  # Iterate through the string with the right pointer
        char_set.add(s[right])  # Add the current character to the set
        if len(char_set) > k:  # If the size of the set exceeds k
            char_set.remove(s[left])  # Remove the leftmost character from the set
            left += 1  # Move the left pointer one step forward
        max_len = max(max_len, right - left + 1)  # Update the maximum length of the substring seen so far
    return max_len  # Return the result

Test your solution

assert lengthOfLongestSubstringKDistinct("eceba", 2) == 3
assert lengthOfLongestSubstringKDistinct("aa", 1) == 2

The above test cases passed, it gives the correct answer.

In this problem, we are able to find the length of the longest substring T that contains at most k distinct characters by using the sliding window approach. The time complexity of this solution is O(n) and the space complexity is O(min(n,k)), because we are using a set to store the distinct characters in the current window, the size of the set is at most k and at most n.

Note that this solution is assuming that the input string and the number k are both valid, if not it may cause errors, so you might want to add some validation before the main part of the solution.