340. Longest Substring with At Most K Distinct Characters - Explanation

Description

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

A substring is a contiguous non-empty sequence of characters within a string.

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Binary Search + Fixed Size Sliding Window

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        if k >= n:
            return n
        left, right = k, n
        
        def isValid(size):
            counter = collections.Counter(s[:size])
            if len(counter) <= k:
                return True
            for i in range(size, n):
                counter[s[i]] += 1
                counter[s[i - size]] -= 1
                if counter[s[i - size]] == 0:
                    del counter[s[i - size]]
                if len(counter) <= k:
                    return True
            return False
        
        while left < right:
            mid = (left + right + 1) // 2
            
            if isValid(mid):
                left = mid
            else:
                right = mid - 1
        
        return left

Time & Space Complexity

Time complexity: $O(n \cdot \log n)$
Space complexity: $O(n)$

Where $n$ is the length of the input string s and $k$ is the maximum number of distinct characters.

2. Sliding Window

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        max_size = 0
        counter = collections.Counter()
        
        left = 0
        for right in range(n):
            counter[s[right]] += 1
            
            while len(counter) > k: 
                counter[s[left]] -= 1
                if counter[s[left]] == 0:
                    del counter[s[left]]
                left += 1
            
            max_size = max(max_size, right - left + 1)
                    
        return max_size

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(k)$

Where $n$ is the length of the input string s and $k$ is the maximum number of distinct characters.

3. Sliding Window II

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        max_size = 0
        counter = collections.Counter()
        
        for right in range(len(s)):
            counter[s[right]] += 1
            
            if len(counter) <= k:
                max_size += 1
            else:
                counter[s[right - max_size]] -= 1
                if counter[s[right - max_size]] == 0:
                    del counter[s[right - max_size]]

        return max_size

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the length of the input string s and $k$ is the maximum number of distinct characters.