Longest Substring with At Most K Distinct Characters

Problem Summary

• Find the length of the longest substring that has $k$ distinct characters

Key Observations

• Need to solve it in one pass $O(n)$

Approach Taken

• because we want a count + unique chars we need hashmap with char to count
• while removing from left, if count is 0 remove the key val altogether
• do a max(cur, end-start + 1) after each addition

Main Concepts Used

• Two Pointers#2. Same Direction Pointers (Sliding Window)

Time & Space Complexity

• Time: $O(n)$ → Reason: One pass
• Space: $O(k)$ → Reason: We are storing characters to count in our hashmap. At most we will be storing $k$ values in our hashmap.

Code

class Solution:
    def findLength(self, str1, k):
        start, max_length = 0, float("-inf")
        map = {}
        for end, end_char in enumerate(str1):
            map[end_char] = 1 + map.get(end_char, 0)
            while len(map) > k:
                # shrink the window from left and remove 1 from count
                left_char = str1[start]
                map[left_char] -= 1
                if map[left_char] == 0:
                    map.pop(left_char)
                start += 1
            max_length = max(max_length, (end - start) + 1)
        return max_length