Array String Hash Map Sliding Window
Intermediate Level

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

The input contains a string text and an integer k. Your task is to find the length of the longest contiguous substring that contains at most k distinct characters.

A substring must be continuous, so characters cannot be skipped.

For example, in eceba with k = 2, the longest valid substring is ece, so the answer is 3.

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) = a
k (int) = 2
Return:
(int) 1

Use a sliding window with a frequency map.

Expand the right side of the window by adding characters. If the window contains more than k distinct characters, move the left side forward until the window becomes valid again.

Whenever the window is valid, update the longest length found so far.

Pseudocode:

function longestSubstringWithKDistinct(text, k):
    if k == 0:
        return 0
    left = 0
    best = 0
    frequency = empty map
    for right from 0 to length of text - 1:
        add text[right] to frequency
        while number of keys in frequency > k:
            decrease frequency of text[left]
            if frequency of text[left] becomes 0:
                remove text[left] from frequency
            left++
        best = maximum(best, right - left + 1)
    return best
Run your code to see the result.