Main Idea:

The main idea is to use a sliding window approach to find the longest substring with at most k distinct characters. We can maintain a window that contains at most k distinct characters and slide the window to find the longest possible substring.

Solution:

def longest_substring_k_distinct(s: str, k: int) -> int:
    # Initialize variables
    max_length = 0
    char_count = {}  # Dictionary to track character frequencies
    left, right = 0, 0

    # Iterate through the string with the right pointer
    while right < len(s):
        # Update character count
        char_count[s[right]] = char_count.get(s[right], 0) + 1

        # If the window has more than k distinct characters, move the left pointer
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

        # Update the maximum length
        max_length = max(max_length, right - left + 1)

        # Move the right pointer to expand the window
        right += 1

    return max_length

# Example usage:
result1 = longest_substring_k_distinct("eceba", 2)
print(result1)
assert result1 == 3
# Explanation: The longest substring with at most 2 distinct characters is "ece".

result2 = longest_substring_k_distinct("aa", 1)
print(result2)
assert result2 == 2
# Explanation: The longest substring with at most 1 distinct character is "aa".

Explanation:

  • We use two pointers (left and right) to represent the sliding window.
  • The char_count dictionary is used to keep track of the frequency of characters within the window.
  • The right pointer moves to the right, and we update the character count.
  • If the window has more than k distinct characters, we move the left pointer to shrink the window until it has at most k distinct characters.
  • We update the maximum length during each iteration.

Time Complexity:

The time complexity is O(N), where N is the length of the input string s. Both the left and right pointers traverse the string once, and each character is processed at most twice (once by the right pointer and once by the left pointer).

Space Complexity:

The space complexity is O(k), where k is the maximum number of distinct characters in the window. The char_count dictionary can have at most k entries. In the worst case, all characters in the window are distinct.