Longest Substring with K Distinct Characters

Given a string s and an integer k, find the length of the longest substring with at most k distinct characters.

Function Signature:

def longest_substring_k_distinct(s: str, k: int) -> int:
    """
    Find the length of the longest substring with at most k distinct characters.

    Parameters:
    - s: A string.
    - k: An integer (1 <= k <= len(s)).

    Returns:
    - int: The length of the longest substring.
    """
    # Your code here

Example:

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".

Note:

• The input string s consists of lowercase English letters.
• The value of k is a positive integer.

Instructions:

• Write the longest_substring_k_distinct function to solve the problem.
• Implement your solution in Python.
• Provide clear comments in your code.
• Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊