I think the reason we don't have to decrease the mostFreq is because mostFreq only affects our answer when it is larger than the previously largest mostFreq?
I don't really understand the reason why we assure that the condition numofreplacement > k is always unmatched after peforming the shrink. For example, given a list = "aaabbc" and k =2, at the final step we have: {a:3,b:2,c:1}, mostfreq =3 => numofreplacement = 3 (> k=2) -> shrink => {a:2,b:2,c:1}, mostfreq = 2 -> numberofreplacement = 5 -2 =3 ( the condition is still satisfied here ). I don't really understand why you don't update the mostfreq variable after performing the shrink :
Thanks Eric for such a crystal clear explanation.
Thanks for the video, Eric! It worth to mention that O(N * 26) is still linear complexity wich asymptotically approaching O(N).
I like this explanation a lot! Helped a ton, thank you. Liked & Subscribed :D
Thank you Eric!
I think the reason we don't have to decrease the mostFreq is because mostFreq only affects our answer when it is larger than the previously largest mostFreq?
Good explanation, you can also just keep a char pointer to most frequent char and get the count using the hashmap
Nikhil M, Thank you very much for your support!
well explained Thank you
Nice Exaplanatoin...Thank you
Glad you liked it
Hi Eric Just want to know how the time complexity becomes O(N*26).could please help me with that understanding
Hi, Thanks for explanation. Could you just go over why did you set the condition as the (right - left +1)? Is it because of the length?
Thank you :)
right - left + 1 gives us a length of our sliding window, we do +1 since index starts to count from 0.
Thank you!
You're welcome!
I don't really understand the reason why we assure that the condition numofreplacement > k is always unmatched after peforming the shrink. For example, given a list = "aaabbc" and k =2, at the final step we have:
{a:3,b:2,c:1}, mostfreq =3 => numofreplacement = 3 (> k=2) -> shrink => {a:2,b:2,c:1}, mostfreq = 2 -> numberofreplacement = 5 -2 =3 ( the condition is still satisfied here ). I don't really understand why you don't update the mostfreq variable after performing the shrink :
What's the complexity of this algorithm?
i would say O(n) for the time and O(26 or n) for the space
@@SHSelect Space usage for the storage of occurrences is always 26 integer values so the space complexity will be constant i.e. O(1)
@@tourniquet3306 shouldn't he use while instead of if for shrinking?
Greatt