Array String Hash Map Sliding Window
Intermediate Level

Implement the longestSubstringAtMostKDistinctLength method that returns the longest substring length with at most k distinct characters.

You are given a string and an integer k. Return the length of the longest continuous substring that contains at most k distinct characters.

The substring must keep the original order and must be continuous. If k is zero, no non-empty substring is allowed.

Example 1
Input:
text (string) = eceba
k (int) = 2
Return:
(int) 3
Example 2
Input:
text (string) = aa
k (int) = 1
Return:
(int) 2
Example 3
Input:
text (string) = aabbcc
k (int) = 2
Return:
(int) 4

Use a sliding window with two pointers.

Expand the right side of the window and count character frequencies. If the number of distinct characters becomes greater than k, move the left side forward until the window becomes valid again. After each valid window, update the maximum length.

This works because every character enters and leaves the window at most once.

Pseudocode:

function longestSubstringAtMostKDistinctLength(text, k):
    left = 0
    answer = 0
    frequency = empty map
    for right from 0 to length(text) - 1:
        frequency[text[right]]++
        while size of frequency > k:
            frequency[text[left]]--
            if frequency[text[left]] == 0:
                remove text[left] from frequency
            left++
        answer = max(answer, right - left + 1)
    return answer
Run your code to see the result.