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