educative.io

Educative

Solution is unclear

k=4
abbccddeee
In the first pass the logic will mark abbccdd (length = 7) as the longest substring with k unique characters.
However, if we drop the first character ‘a’ then longest substring will be bbccddeee (length = 9)

How does shrinking the window from left of the same window "abbccdd " and not incrementing it from right will find a longer substring with k or less unique characters? If we keep shrinking abbccdd from left
i-e abbccdd
then bbccdd
then bccdd
then ccdd

, the substring has to be shorter than the one already found "abbccdd ", correct?

I am having trouble understanding how does the official solution cover this case?


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Longest Substring with maximum K Distinct Characters (medium) - Grokking the Coding Interview: Patterns for Coding Questions

Hi @bee1!
Actually we don’t have to shrink the window from both sides. We are shrinking the window from left and For loop incrementing it from right. According to the solution, when we reach the point in the shrinking process when we have unique characters fewer than K in the window, we start incrementing it from the right side.

1 Like

thx Adeel,
I read the solution again and it does shrink from the left while incrementing to right solving the problem I asked.

thanks


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Fruits into Baskets (medium) - Grokking the Coding Interview: Patterns for Coding Questions

2 Likes