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) =
ecebak (int) =
2Returns (int)
3Example 2
Input
text (string) =
aak (int) =
1Returns (int)
2Example 3
Input
text (string) =
aabbcck (int) =
2Returns (int)
4Use 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 answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run