educative.io

Longest Substring with Same Letters after Replacement (hard)

Courses
,
#1

https://www.educative.io/collection/page/5668639101419520/5671464854355968/6497958910492672

Hi I have a query regarding the solution. maxRepeatLetterCount here is the repeat count of the letter which repeated maximum times in window [windowStart, indowEnd] . So when wStart moves to right(shrinks) why maxRepeatLetterCount is not updated ? should not we keep track of the maxRepeatLetterCount throught some maxHeap ?

2 Likes
Can't understand why we don't calculate the maxRepeating for each window
#2

@Indrajit_Mitra,

maxRepeatLetterCount refers to the global maximum of any letter repeating. It is NOT the max repeat count in the current window. We need to track only the overall maximum count for our algorithm. See the following line, where we keep the ‘max’ of the current maxRepeatLetterCount and the frequency count of the current letter.

maxRepeatLetterCount = Math.max(maxRepeatLetterCount, letterFrequencyMap.get(rightChar));

Hope this answers your question.

2 Likes
#3

We’ll also keep track of the letter which is repeating the most in the current window (let’s call it maxRepeatLetterCount ).

According to this sentence, maxRepeatLetterCount is the max count in current window.

1 Like
#4

@LH_RV, sorry about the confusion. As we stated above, ‘maxRepeatLetterCount’ is the count of the maximum repeated letter in ANY window.

The real confusion arises from the fact that when we shrink the window we are not updating this count (which makes it global, hence, it is the maximum count for any window). Why we don’t need to update this count when we shrink the window? The answer: In any window since we have to replace all the remaining letters to get the longest substring having the same letter, we can’t get a better answer from any other window even though all occurrences of the letter with frequency ‘maxRepeatLetterCount’ is not in the current window.

7 Likes
#5

This was throwing me off as well, but this explanation clears things up for me. Thanks so much! @Design_Gurus

1 Like
#6

Once we have reached the max window, where maxRepeatCharacter is max, after that we are not decrementing the window. So window size for all next iteration will be same. It can only go up.

2 Likes
#7

It could be probably be wrong to call it as a “global” maximum repeating count. In the following case, “global” max repeating count would be 7 for ‘a’, but in the window covering all b’s we consider max count of 5 not 7. (we reduce frequency of ‘a’ as windowStart moves right)
System.out.println(CharacterReplacement.findLength(“aaaaabbbbaabb”, 2));

If it spinning your head, better to change the code you like to make it clearer.

#8
#9

@Viraj_Bhosle @Design_Gurus won’t change the code may be due to the view that ‘my code is always right if people are confused let them be’. I always get confused when I revisit this question. God forbid if this question comes to my interview I will be pulling my hair explaining to the interviewer. But, yeah, code won’t get changed!