Longest Substring with At Most K Distinct Characters

Sliding WindowHash Map

25 min

Problem Statement

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

Example

Example 1:

Input: s = "eceba", k = 2

s: "eceba", k: 2

Output: 3

The substring is "ece" with length 3.

Solution

This problem can be solved using a sliding window and a hash map. The hash map will store the frequency of characters in the current window. We expand the window by moving the right pointer. If the number of distinct characters in the map exceeds `k`, we shrink the window from the left until the condition is met again.

Algorithm Steps

Initialize `maxLength` to 0, a left pointer `l` to 0, and a hash map `charCount`.
Iterate through the string with a right pointer `r`.
Add the character `s[r]` to the hash map and increment its count.
While the number of distinct characters in the hash map is greater than `k`:
Decrement the count of the character `s[l]` in the map.
If the count becomes 0, remove the character from the map.
Increment `l`.
Update `maxLength` with the maximum of `maxLength` and the current window size (`r - l + 1`).

Longest Substring with At Most K Distinct Characters

Sliding Window with Hash Map

Progress1 / 1

Ready to start the visualization

Hash Map (char: count)

Max Length

Longest Substring with At Most K Distinct Characters Solution


from collections import defaultdict

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        char_count = defaultdict(int)
        l = 0
        max_len = 0
        
        for r in range(len(s)):
            char_count[s[r]] += 1
            
            while len(char_count) > k:
                char_count[s[l]] -= 1
                if char_count[s[l]] == 0:
                    del char_count[s[l]]
                l += 1
            
            max_len = max(max_len, r - l + 1)
            
        return max_len