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