LeetCode Solutions Blog

Longest Substring with At Most K Distinct Characters

Number: 340

Difficulty: Medium

Paid? Yes

Problem Description

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

Key Insights

Use the sliding window technique to efficiently scan through the string.
Maintain a hash table (or dictionary) that keeps track of the frequency of characters in the current window.
When the number of distinct characters exceeds k, increment the left pointer to shrink the window until the condition is met.
Update the maximum length of valid substrings throughout the process.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as each character is processed at most twice (once when expanding the window and once when contracting it).
Space Complexity: O(min(m, k)), where m is the size of the charset (or number of unique characters in s), since at most k+1 keys are stored.

Solution

This problem is solved using the sliding window technique. The algorithm keeps track of a window defined by two indices (left and right pointers). A hash map is used to count the frequency of each character in the current window. As the right pointer extends the window, the count of the character is incremented. When the count of distinct keys in the map exceeds k, the left pointer is moved forward while decrementing the count of the leftmost character, until the condition is restored. The maximum window length encountered is recorded and returned as the result.

Code Solutions

# Python solution for Longest Substring with At Most K Distinct Characters

def longest_substring_with_k_distinct(s: str, k: int) -> int:
    # Handle edge case: if k is 0, no valid substring exists
    if k == 0:
        return 0
    
    # Dictionary to store frequency of characters in the current window
    char_count = {}
    left = 0  # Left pointer for the window
    max_length = 0  # Variable to track the maximum length found

    # Iterate through the string using the right pointer
    for right in range(len(s)):
        # Add/update the count of the current character in the dictionary
        current_char = s[right]
        char_count[current_char] = char_count.get(current_char, 0) + 1

        # If window contains more than k distinct characters, shrink from the left
        while len(char_count) > k:
            left_char = s[left]
            char_count[left_char] -= 1
            # Remove the character count if it becomes 0
            if char_count[left_char] == 0:
                del char_count[left_char]
            left += 1
        
        # Update the maximum length of the valid window found so far
        max_length = max(max_length, right - left + 1)

    return max_length

# Example usage:
# s = "eceba", k = 2
# print(longest_substring_with_k_distinct(s, 2))  # Output: 3