Longest Substring with At Most K Distinct Characters

Patrick Leaton
Published: Sept. 8, 2021, 8:20 p.m.
Problem Description

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

 

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.

 

Constraints:

  • 1 <= s.length <= 5 * 10^4
  • 0 <= k <= 50

 

The description was taken from https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        left, right = 0, 0
        longest = -1
        window = {}
        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1
            right += 1
            while len(window) > k:
                if window[s[left]] == 1:
                    del window[s[left]]
                else:
                    window[s[left]] -= 1
                left += 1
            longest = max(longest, right - left)
        return longest

Problem Explanation

The question requires us to return the length of a specific substring that satisfies a certain constraint.

When we see that requirement, we know that a sliding window may be a good approach.

What we can do is have two pointers that signify the left-bound and right-bound of our sliding window.  We will use a hashmap to track the distinct characters along with their count, and if we have more than k distinct characters within our hashmap, we know that we need to shrink the left side of the sliding window.  

That is the general template for sliding window problems, we will expand the right side until our window is no longer valid in which case we will shrink the left.  In this case, the window will no longer be valid if we have more than k distinct characters inside of it.

Let's start by initializing our left and right pointers to zero, the first index of the string.

        left, right = 0, 0

 

We will set our running, longest substring counter to negative one.  We want to make sure we choose the initial value of a running count that will be outside the bounds of the given constraints since the goal is for this to be overwritten by a greater value later. 

        longest = -1

 

We will also use a hashmap to signify the window.  The hashmap will contain each distinct character within the window and its frequency.

        window = {}

 

Now let's begin traversing the string.

We will continue until the right pointer has gone past the end of the string.

        while right < len(s):

 

Just like other sliding window problems, our right pointer will be in charge of throwing values into the window.  The left will be in charge of evicting values from it.

Let's throw the character at the right pointer into the window then expand.

            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1
            right += 1

 

We can continue expanding until our window does not satisfy the given constraint, when we have more than k distinct characters in our window.

Now we need to start shrinking it before we expand again.

While the number of distinct characters in the window is greater than k, we will remove the character at the left pointer from the window by decrementing the frequency of the character in our hashmap and incrementing the left pointer.  But remember, if we leave character keys in the hashmap when their frequency gets decremented to zero, that character will stay in our window still.  To fix this, we will check if the character frequency is zero and delete it from the hashmap if it is.

            while len(window) > k:
                if window[s[left]] == 1:
                    del window[s[left]]
                else:
                    window[s[left]] -= 1
                left += 1

 

Once we have made sure our window is of the given constraint, we will test it against the current longest substring with at most k distinct characters.

            longest = max(longest, right - left)

 

Once we have slid our window across the entire string, we will return the longest substring we found of the given constraint.

        return longest

 

Additional Notes

This is the same exact solution for Longest Substring with At Most Two Distinct Characters, the only difference is the highlighted portion where we shrink the window if we have more than two distinct characters instead of k.
 
We got a two-for-one question special! 
 
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
#O(N) Time, O(1) Space
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        left, right = 0, 0
        longest = -1
        window = {}
        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1
            right += 1
            while len(window) > 2:
                if window[s[left]] == 1:
                    del window[s[left]]
                else:
                    window[s[left]] -= 1
                left += 1
            longest = max(longest, right - left)
        return longest