Longest Repeating Character Replacement - Leetcode 424 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/longest-...
0:00 - Read the problem
2:28 - Drawing Explanation
16:48 - Coding Explanation
leetcode 424
This question was identified as a google interview question from here: github.com/xizhengszhang/Leet...
#character #replacement #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@user-vk1tc6cu5t]

hi Neetcode In you Website Code Submission isn't auto Updating we need to refresh inoreder to get the latest submission

[@elheffe2597]

I love that you always start with the most obvious brute-force solution first, and then show how to optimize it after. It makes these problems so much easier to digest.

[@aznguyener]

Also for interviewees, its good to talk this through out loud in an interview so they can see your thought process!

[@jeremyyeo7092]

For those who are struggling to understand the optimisation with maxf, here is how i understood it: For a substring to be valid, we need window_length - maxf

[@_dion_]

probably the best possible breakdown. thank you, jeremy.

[@JamesBond-mq7pd]

he said same thing at 14:00 "the main idea is this ..."

[@user-nj1xh8ot3f]

@@JamesBond-mq7pd I came to the comments because I was struggling to understand Neatcode's explanation of why we don't need to update the max frequency. The comment above explains it in a much clearer way IMO

[@praneethkaturi9321]

@@user-nj1xh8ot3fI agree. The wording here is better!

[@ichigo9688]

@neetcode needs to pin this comment.

[@kartiksoni825]

Please keep doing this for more Leetcode problems - nobody explains them like you do. This channel deserves so many more subscribers!

[@whitest_kyle]

This is one of those problems that literally makes no sense to me, like why would we ever need to do this? Tech hiring is so weird...

[@jessiz-]

Having the visualization was really helpful and now the problem seems much simpler. I like how you also explained the max frequency count optimization and the logic behind it. Thanks for your videos!

[@SandeepKumar16]

If someone is wondering like me - "Why is while loop and if statement, both giving correct result?" The answer is: Suppose we use while loop. It will enter the while loop, only when (strLength - maxFreq) is just greater than k by " 1 ". And as soon as this happens, we decrease our String size by 1, by shifting the left pointer. So, now strLength - maxFreq = k. So, while condition will break. In short- While condition will be satisfied only once. So, why not use an "if" instead. Hope this helps someone. Thanks @NeetCode. You've done a great job.

[@user-su9vz7ww6p]

thank you, that's exactly what i was looking for in comments, i did wonder why my if statement worked actually

[@allenlam5210]

thank you

[@jeremyyeo7092]

In response to Sandeep's comment about the while loop: I believe there's a misunderstanding. The condition (window_length - highest_freq) > k can be satisfied more than once for a given window. Consider the example s="ABABACB", k=2: We expand the window until it reads "ABABAC". Now, let's evaluate the condition: "ABABAC" window_size=6 max_freq=3 window_size−max_freq=3, which is greater than 2. So, the condition is satisfied the first time, and we advance the left pointer resulting in "BABAC". Re-evaluate: "BABAC" window_size=5 max_freq=2 window_size−max_freq=3, still greater than 2. The condition is satisfied for the second time, and we advance the left pointer to get "ABAC". Now, the condition is no longer satisfied. From this example, we see that the condition can be satisfied multiple times, contrary to the claim that it will only be satisfied once. The real reason an "if" statement suffices is that even if the resulting window after the "if" condition is executed might still be invalid, its size will never surpass the maximum window size found up to that point. We are only shrinking the window by 1 by moving the left pointer while keeping the right pointer static. This ensures the correctness of the solution.

[@fujiantao7680]

I think it should make it more clear on why we could move right point or left point, when "window_size−max_freq" is larger than K, moving right point will get no chance to make "window_size−max_freq" smaller, either both window_size + 1 and max_freq + 1, or just window_size + 1 and max_freq keeps the same, while moving left point will reduce window_size by 1, while max_freq could be the same or max_freq-1, that said, moving left will get a chance to make "window_size−max_freq" smaller, that it why when "window_size−max_freq" is larger than K, we just need to move left pointer. However, since we are finding the maximum result, so there is no chance to make it better if we shrink the window by pop left and keep right the same, we have to pop left and then move the right and try to see if we can find better solution. However if we just pop left once as the example above, and still not able to get "window_size−max_freq

[@HoangTran-kf1ij]

thanks you🥰@@fujiantao7680

[@joydeeprony89]

there are many channel who has created the content for this problem but you only have explained why do we no need to update maxF in while loop. No fake knowledge , you are pure talent.

[@kristofferpanahon9913]

You're the best out there - thank you for everything!

[@ladyking83]

it's not easy to get one's head around this one, thanks for working it through!💚

[@lifeofme3172]

True, thanks @Neetcode that slow explanation really helped my brain

[@Axl124124]

yeah this one is tough to think about.

[@celialiang1485]

Very helpful video. I learned how to build up the idea from scratch. It's needed especially when you explain to the interviewer in a tech screening. Thanks a lot!

[@AkshayAmbekar-kd8zm]

The optimization with maxf is so freaking genius! Thanks for taking time to make this. Grateful🙏

[@vudat1710]

the best of the best. I'm learning a lot from you. Huge credit to you my guy!

[@anmolpansari9817]

Loved the second approach.. Optimized Channel - No complexity in finding good videos .. this defines NeetCode

[@triscuit5103]

fantastic explanation, the first time I get very clearly why we don't need to decrement the maxF var. much love to you, some hugs and kisses as well, but in a very professional and thankful manner.

[@shriyanshkhandelwal3988]

I love the way you explain and even teaching DSA with python. Loved it TY

[@RanjuRao]

Awesome as always !! Love to watch your videos ! Please do the system design videos as you're very good in explaining concepts :)

[@anishr8017]

You're doing an awesome job!! Thank you! Keep up the work, you're helping a lot of us!

[@madhavoberoi6441]

Thanks a lot for this solution, I came up with a bit complex recursive + DP solution with O(n*n) complexity and was proud of myself unless I saw your solution. Also keep up the great work you're doing!

[@VivekMishra-hd7mg]

He gave the best explanation. really good man!! This channel will grow a lot in future.

[@jinyang4796]

Thank you so much for this video! Loved the part from 12:10 onwards. Just adding on, I realised one possible small tweak is that we can use an if condition, instead of a while condition. Saw the following in one of the LC's comments and felt it is really enlightening: "We have a "longest" window already so finding another one of the same size is not helpful. Yeah, we might shrink the window, then extend it, then find another window of the same size as longest but in the end we will see no improvement as long as it it's just as long as longest."

[@NeetCode]

Good point

[@rosenoire9670]

thanks! I was stuck at this little detail as well... although as with other LC problems, it still does not click 100% for me lol.

[@del6553]

If current substring is not valid, then there exist a previous valid substring of currSize-1 (you can prove this by contradiction for example) Which implies the final answer >= currSize-1, so now we're only interested in finding res >= currSize Therefore we only have to shift left pointer by 1, effectively shifting the current window of currSize by one when we're in the next iteration

[@saravalls26]

The max(count.values()) amazed me, I had written an extra function to look for that. You're the GOAT of this man, thanks a lot for your hard work ♥

[@vishtree]

Its easier to understand the final optimisation, if you simply replace while condition with if condition. In that case, it simply means that if window_length - maxf > k, its time to shift the window by one position to the right, because you have exceeded the number of replacement you can do in current window.

[@michaelmarchese5865]

Great insight. The while loop was unnecessary all along and just overcomplicated both the overall solution and the maxf optimisation.

[@niteshmgs7569]

Great job mate, very good explanation... keep working, your channel will definitely grow. It's the best

[@emmisae-ueng8976]

The explanation is really good, easy to follow and understand.

[@MaxFung]

This explanation is far better than Leetcode's editorial solutions, which are far too dense and wordy to be of much use to leetcode students. Only the most focused and motivated would be able to parse through that crap. Thanks for sharing this with the world, you're making my life a lot better.

[@gokulnaathbaskar9808]

The first approach was very easy to understand, thank you so much

[@bens9962]

Hey, just want to say that you're the best :D Your visualization makes a lot of difference. Thank you!

[@aryanyadav3926]

Well explained! The O(n) solution was really tricky.

[@seanwayland]

An amazing channel. Comments in the code solution would make it easier to understand and if I was an interviewer more likely to give the candidate a job.

[@ijavd]

My personal notes on why the O(n) solution works: This is our equation: length - maxFreq

[@qwertyasdf6301]

The reason you have given for why the maxfreq need not be updated in case of a decrease is that the result doesn't change. Which is understandable because the length of the substring did not increase. But how to answer this: Not updating the maxfreq will mess up the valid string window and subsequent manipulations of the window? There's no explanation on why the subsequent manipulations of the string window will still be correct given the maxf doesn't hold the accurate value.

[@publich]

@@qwertyasdf6301 I have the same question, did you figure out why not updating maxf doesn't mess up the window manipulations?

[@h3ckphy246]

@@qwertyasdf6301 "Not updating the maxfreq will mess up the valid string window and subsequent manipulations of the window?" That's not true. It won't mess it up. The algorithm works the same. Just take an example string and manually perform all the actions with and without the optimization. You will see that sliding window are the same in each case and on each step. Personally I tried this string: AAABBCCDAA. Your window will grow to the size of 6 and keep sliding until it reaches the end. It's hard to describe everything in the comment sections without illustrations, but drawing with pen and paper helped me to understand it. You (and the others reading this) should do the same.

[@algosavage7057]

Thanks a lot for your explanation. I was so curious about solving in more efficient than O(26*n).

[@daddac]

i cant figure out why max frequency works even the char might out of sliding window... until i watch this video. awesome indeed. thanks for posting such concise and clean video!!

[@downtownsocialite1206]

Absolutely clean explanation, good work!

[@shwethaks7994]

Awesome explanation as always. It would be really great if you can do system design videos as well. You are really good.

[@alcatraz5161]

the best part about this solution is how it is character agnostic a problem like this you'd want to think about chaining bits and pieces of character sub-strings as long as the gap size between them is under current value of k but this removes the necessity for that well solved and thank you :)

[@adityaojha2701]

Thanks for such a nice and clear explanation!!

[@nimeshpareek953]

Man you just explained it this easy like I watched the video and write pseudocode on pen and paper and coded it and in single go submitted

[@n1724k]

After listening to your second solution, I coded it before looking at your code, and got completely same one. Kind of proud about it!

[@dorondavid4698]

You could also stop the algorithm if the R is at the furthest right as when you shift over the Left pointer; if r-l+1

[@jawakar8266]

This doesn't work when s='ABAA' k=0, the result should be 2 but you will get 1

[@ujjvalsharma5055]

Wonderful solution!! Keep making videos! You will definitely get more subscribers!!

[@biswajitmahalik4134]

thanks a lot, man! I saw the codes n wasn't able to figure out why aren't they downgrading max freq...n you explained it so nicely .

[@dgvj]

To comeup with the condition was really difficult.Thanks a ton for the awesome explanation.

[@phuongdh]

Finally someone who explains why we didn't need to decrease the max_frequency, other videos offer no explanation.

[@prunesalad]

thanks for going deep on the O(1n) case, very interesting

[@StLegend950111]

Dude, you are awesome. Thanks for your clean explanation.

[@smartlab5173]

You are the Greatest of the Great! Champion! Honestly, words are not enough to thank you. Your clarity of explanation is Mind Blowing. God bless you! :-)

[@oladapoajala6518]

Nice video, because moving the left pointer once would always make the condition "(r - l + 1) - max(count.values()) > k" True, you can replace the inner while loop with an "if" statement to better show that the algorithm is linear in time.

[@free-palestine000]

Wow this took me so long to understand, thank you

[@sandeshsrinivas4177]

This approach is far more superior than any other solution.

[@protyaybanerjee5051]

Thank you for creating this channel.

[@titashmandal8338]

Very good explanation. Thank you so much for sharing.

[@arthurasanaliev]

wow, such an elegant solution, thanks for explanation!

[@avipatel1534]

Just one minor thing, you could replace the inner while loop with an if statement because you would be iterating a max of 1 time in that while loop

[@mihirmodi1936]

Yes Right!! But It will be good if you explain it that why we don't need loop. (Try with this example s="AABCDAAAAMN" k=2) Here, We need to execute loop multiple time, but still if will give correct ans.

[@shantanukumar4081]

Great Explanation !!!

[@quirkyquester]

bruhh,, you make this difficult questions seems so easy, thank you!

[@kuoyulu6714]

another great day, with another great neetcode video

[@MrQuadraaa]

This is a great explanation, thanks a lot.

[@votanlean]

Brute Force: ans = 0 for i in range(len(s)): for j in range(i, len(s)): charCnt = Counter(s[i:j+1]) for cnt in charCnt.values(): if j - i + 1 - cnt

[@wise_wealth_builders]

Found this channel awesome!!!! I have some idea each time but turn out I cannot figure out the solutions. It would be nice if you can walk through your thinking process when you are doing a question.

[@pragyasingh5880]

Damn this is the best explanation of this problem so far. Thanks for this awesome video!

[@NeetCode]

Happy it's helpful! 🙂

[@abhirupchakravarty8508]

if we store the curr max f and the char that gives it, when we add a new char in the window, we can increment and check its frequency, and if that's higher than max f, we can update both the most f char and the max f to the newly added char (similarly, in decrements, but as NC pointed out, that's not required)

[@mr6462]

Thanks for the O(n) explanation, very clear!

[@idontneedthis56]

Hi @neetcode Is it possible to create a playlist of sliding window problems, from the problems that you have already solved. Much like how you have the blind-75 playlist, medium problems playlist etc. That kind of categorization would be enormously helpful as well. Likewise, a playlist marked HARD would be very useful as well I also wanted to give you a long overdue shoutout for your videos. They are, without question, the nest resource for leetcoding out there. Keep em coming Just wanted to make a long overdue shoutout to your channel It has some of the best content, with

[@atharvakulkarni3007]

Awesome explanation loved it 😁

[@anu8928]

Amazing explanation🙏🏼

[@pritampawar6478]

great explanation easy to follow 🔥🔥🔥🔥

[@LunaFlahy]

Very smart! I think Rolling hash is an efficient way to save time optimization!

[@yuanpengli5704]

Absolutely love your teaching style

[@NeetCode]

Thanks :)

[@Jonathanwu_tech]

thank you!! the tutorial is so good!!

[@ayeshaadhikari6123]

Thanks a lot! Very helpful!

[@vibhushajain6363]

awesome explanation. thanks!

[@armaan1610]

i was stuck at that mostf thing for 1 whole day.... thanks for adressing and explaining it

[@user-lj9oq8rb8d]

I have understood only your explanation of this problem, thank!

[@onlylikenerd]

I spent over 3 hours solving this on my own. My solution was 80 lines of code. Here I am looking at your solution mind blown.... lol. Boy did I over complicate things.

[@pabloarkadiuszkalemba7415]

Another way of doing it is mantaining a max heap to get the max value, so it would be O(log(26))

[@rsKayiira]

Excellent explanation!!

[@rajeshdas2295]

Nice Explanation!!!

[@rohandevaki4349]

how do you approach to tough problems like this?and how can we improve our thinking and optimise the code? i am not even able to think of a bruteforce approach for this, it is that hard.

[@cschandragiri]

this one is hard

[@yuurishibuya4797]

Keep solving, that will create a hash map in your brain, problem pattern - solution. Then when u look at different problems, you will know how to solve in O(k) or O(log(n))

[@MrjavoiThe]

@@yuurishibuya4797 how can you solve more, if you can’t solve anything and trying to solve by your own confuses you more and brings the habit of doing horrible solutions.

[@MrjavoiThe]

@@yuurishibuya4797 isn’t better to understand the different solutions and patterns and then try to apply those yourself on similar problems?

[@udaykulkarni5639]

Practice and consistency Dont worry about the optimization. Optimization usually requires a trick that you learn when you keep solving problems. Try to come up with brute force solution within say 30 mins. If you cant. Just look at solution. Code it yourself. Understand it thoroughly. Make a note of it. Come back to same problem after 1 week. Can you still code it? This time you looked at problem differently. And same thing happens when you keep doing it. But but but. It takes lot of patience and discipline. You will feel like giving up and thinking its not for you. But remember - IT IS DIFFICULT AND IT TAKES TIME. YOU WILL MAKE IT CHAMP!! GOOD LUCK

[@tomonkysinatree]

I think the easiest way to think about the maxf optimization is this: the res (length) is not updated unless the condition len - maxf

[@leonardmensah6781]

This is what we call a G.O.A.T explanation !!!!!!

[@ritwik121]

your video saved me. thanks a lot

[@lokeswaranaruljothy8100]

Finally, I was not the only one who don't know the last approach, even neetcode does not know about it🤣

[@EranM]

Use max heap to save the biggest character :> You can also save a map for the nodes in the heap for easier "increase/decrease key" operations. Any priority queue will suffice.

[@justforfun4680]

How I understood maxf is that: Only if you can get a bigger maxf (under constraint of window_length - maxf

[@m_jdm357]

From what I saw it can't get simpler than the solution NeetCode provided. Thank you for the simplest solution. No, no, no this thing is not solvable if you don't know the solution.

[@zeroblade8315]

why does both an if and a while loop work for the solution, for shifting the left pointer?

[@sukinkumar7042]

Incredible. Especially the piece of math from 13:53! Too good :)

[@karlshtolz1066]

Thank You) this answer help me on ProgrammingCup

[@noelcovarrubias7490]

I'm super curious @NeetCode and I hope you can answer but. What did you study to arrive at solutions like the one for this problem? What books did you read, how much time did you spend at each problem? Did you look at solutions and then learned from them or what? I really would like to know because it blows my mind the way you explain things and arrive at solutions and if I could do a fraction of what you're able to, I would be a happy man. Thank you

[@Joyddep]

Thank you very much!

[@satyajeetkumarjha1482]

Great explanation.Just that we don't need while over there and "if" should work fine .

[@Mohib3]

Great explanation. Easy to understand after you explained it but how does one even come up with that solution in an interview if they never saw this problem before.

[@legendsmnd]

Correct me if I'm wrong, you do not need to decrement the max frequency variable because that won't affect the result. It is an overestimation and the following characters will produce the same result until there is an update in the max frequency, which increases the result.

[@jeremiahthomas7594]

good stuff man

[@chetan788]

Did you figure out all solutions on your own? I could only figure out only 2 or 3 out of 14 mediums I have done so far. What am I missing? How could I improve?

[@Amy-601]

Omg 😳! Where have you been! You should see the long winded, frankly, convoluted explanations on some websites- it’s a travesty! This is so very well explained! Super useful! So Thank you 😊! - Amy

[@thomasmcnutt252]

incredible vid!

[@NickolasCavagnaro]

We can further optimize from O(n * m) where m is the number of characters to just O(n) where n is the size of the input array. Once we have a window of size k + majority count, we don't need to update the majority count as a result of shrinking the window as long as we only increase the result when we have encountered a higher majority count than before. And before we reach a window size of k + majority count, the majority count will be correct because it will not include characters from before the window. But once we do have a window of size k + majority count, we can always keep the window size the same, only increasing it if we encounter a higher majority count than before, and only updating the result when we have updated the window size. This way, we don't need to go through the counts of each character, we only need to update the majority count to be the highest majority count we have seen in a window so far.

[@huseyinbarin1653]

I liked this question a lot.