educative.io

Educative

Aaadbbctbb how is this input handled

aaadbbctbb, k=2
The max repeating character in a single window is “a” which is 3.
bb becomes the max repeating character only at the end of the string(2+2=4). Since the solution is forward looking i-e it either shifts the window right or expand the window, how does it know ct are the two characters to replace when its processing the bb appearing at the end of string.
The solution correctly calculates the answer as 6. I just want to understand how.

when processing “aaa” logic thinks 3 is the max repeating character. It replaces the next 2 character and we have longest substring length = 5.

It then processes the first bb. bb repeats 2 times which is less than 3 (where 3 is the repeat frequency of letter “a”) so it will ignore it.

It will then eventually reach the end bb. how does it now know to join the former bb with the end bb by replacing the “ct” by “b” to get the correct answer 6?


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Longest Substring with Same Letters after Replacement (hard) - Grokking the Coding Interview: Patterns for Coding Questions

Hi @bee1,
I think you get a little confused. When the non-repeating characters count becomes equal to K then we start moving the start-end of the window. When the starting-end of the window is at 4 and ending-end of the window is at 9 then it shows you that it contains 4 repeating characters and 2 non-repeating characters.

I suggest you try the solution by printing the values of variables like max_repeat_letter_count, window_end, and window_start. It will be really helpful to understand the working of the solution.

Thanks, I hope this answer helps :grin:.