🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
@user-vk1tc6cu5t7 ай бұрын
hi Neetcode In you Website Code Submission isn't auto Updating we need to refresh inoreder to get the latest submission
@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_8 ай бұрын
probably the best possible breakdown. thank you, jeremy.
@JamesBond-mq7pd7 ай бұрын
he said same thing at 14:00 "the main idea is this ..."
@user-nj1xh8ot3f4 ай бұрын
@@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
@praneethkaturi93214 ай бұрын
@@user-nj1xh8ot3fI agree. The wording here is better!
@ichigo96883 ай бұрын
@neetcode needs to pin this comment.
@elheffe25972 жыл бұрын
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.
@aznguyener10 ай бұрын
Also for interviewees, its good to talk this through out loud in an interview so they can see your thought process!
@kartiksoni8252 жыл бұрын
Please keep doing this for more Leetcode problems - nobody explains them like you do. This channel deserves so many more subscribers!
@whitest_kyle2 жыл бұрын
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...
@joydeeprony892 жыл бұрын
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.
@jessiz-2 жыл бұрын
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!
@kristofferpanahon99132 жыл бұрын
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
@Axl12412411 ай бұрын
yeah this one is tough to think about.
@celialiang14853 жыл бұрын
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!
@SandeepKumar162 жыл бұрын
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-kf1ij11 ай бұрын
thanks you🥰@@fujiantao7680
@AkshayAmbekar-kd8zm10 ай бұрын
The optimization with maxf is so freaking genius! Thanks for taking time to make this. Grateful🙏
@vudat17102 жыл бұрын
the best of the best. I'm learning a lot from you. Huge credit to you my guy!
@anmolpansari98172 жыл бұрын
Loved the second approach.. Optimized Channel - No complexity in finding good videos .. this defines NeetCode
@taskmaster50322 жыл бұрын
This example helped me understand why we don't need to update the maxf value if it is not greater than the previous value, hope it helps someone: characterReplacement("aabcdbb", 2); aabcdbb - aabc (4) # a is most frequent char, maxf = 2 abcdbb - abcd (4) # a, b, c, d, maxf still equals 2 bcdbb - bcdb (4) # bcdbb - bcdbb (5) # maxf increased
@jinyang47962 жыл бұрын
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."
@NeetCode2 жыл бұрын
Good point
@rosenoire96702 жыл бұрын
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.
@del65535 ай бұрын
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
@triscuit51032 жыл бұрын
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.
@RanjuRao3 жыл бұрын
Awesome as always !! Love to watch your videos ! Please do the system design videos as you're very good in explaining concepts :)
@shriyanshkhandelwal3988 Жыл бұрын
I love the way you explain and even teaching DSA with python. Loved it TY
@anishr80173 жыл бұрын
You're doing an awesome job!! Thank you! Keep up the work, you're helping a lot of us!
@madhavoberoi64413 жыл бұрын
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-hd7mg2 жыл бұрын
He gave the best explanation. really good man!! This channel will grow a lot in future.
@emmisae-ueng89763 жыл бұрын
The explanation is really good, easy to follow and understand.
@gokulnaathbaskar98082 жыл бұрын
The first approach was very easy to understand, thank you so much
@MaxFung5 ай бұрын
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.
@niteshmgs75693 жыл бұрын
Great job mate, very good explanation... keep working, your channel will definitely grow. It's the best
@saravalls262 ай бұрын
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 ♥
@bens99622 жыл бұрын
Hey, just want to say that you're the best :D Your visualization makes a lot of difference. Thank you!
@algosavage70572 жыл бұрын
Thanks a lot for your explanation. I was so curious about solving in more efficient than O(26*n).
@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?
@h3ckphy24626 күн бұрын
@@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.
@seanwayland2 ай бұрын
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.
@dorondavid46982 жыл бұрын
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
@jawakar82662 ай бұрын
This doesn't work when s='ABAA' k=0, the result should be 2 but you will get 1
@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
@n1724k8 күн бұрын
After listening to your second solution, I coded it before looking at your code, and got completely same one. Kind of proud about it!
@downtownsocialite12062 жыл бұрын
Absolutely clean explanation, good work!
@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 .
@alcatraz51615 ай бұрын
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 :)
@adityaojha27013 жыл бұрын
Thanks for such a nice and clear explanation!!
@dgvj Жыл бұрын
To comeup with the condition was really difficult.Thanks a ton for the awesome explanation.
@daddac2 жыл бұрын
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!!
@aryanyadav39262 жыл бұрын
Well explained! The O(n) solution was really tricky.
@shwethaks79942 жыл бұрын
Awesome explanation as always. It would be really great if you can do system design videos as well. You are really good.
@phuongdh2 жыл бұрын
Finally someone who explains why we didn't need to decrease the max_frequency, other videos offer no explanation.
@avipatel15342 жыл бұрын
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.
@prunesalad2 жыл бұрын
thanks for going deep on the O(1n) case, very interesting
@oladapoajala651820 күн бұрын
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.
@ujjvalsharma50553 жыл бұрын
Wonderful solution!! Keep making videos! You will definitely get more subscribers!!
@StLegend950111 Жыл бұрын
Dude, you are awesome. Thanks for your clean explanation.
@pragyasingh58802 жыл бұрын
Damn this is the best explanation of this problem so far. Thanks for this awesome video!
@NeetCode2 жыл бұрын
Happy it's helpful! 🙂
@smartlab51732 жыл бұрын
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! :-)
@abhirupchakravarty85088 ай бұрын
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)
@titashmandal83382 жыл бұрын
Very good explanation. Thank you so much for sharing.
@free-palestine0002 жыл бұрын
Wow this took me so long to understand, thank you
@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.
@protyaybanerjee5051 Жыл бұрын
Thank you for creating this channel.
@sandeshsrinivas4177 Жыл бұрын
This approach is far more superior than any other solution.
@MrQuadraaa Жыл бұрын
This is a great explanation, thanks a lot.
@quirkyquester25 күн бұрын
bruhh,, you make this difficult questions seems so easy, thank you!
@arthurasanaliev Жыл бұрын
wow, such an elegant solution, thanks for explanation!
@shantanukumar40812 жыл бұрын
Great Explanation !!!
@idontneedthis562 жыл бұрын
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
@ayeshaadhikari61232 жыл бұрын
Thanks a lot! Very helpful!
@yuanpengli57042 жыл бұрын
Absolutely love your teaching style
@NeetCode2 жыл бұрын
Thanks :)
@Jonathanwu_tech Жыл бұрын
thank you!! the tutorial is so good!!
@kuoyulu671411 ай бұрын
another great day, with another great neetcode video
@user-lj9oq8rb8d Жыл бұрын
I have understood only your explanation of this problem, thank!
@armaan16102 жыл бұрын
i was stuck at that mostf thing for 1 whole day.... thanks for adressing and explaining it
@mr64622 жыл бұрын
Thanks for the O(n) explanation, very clear!
@zeroblade83152 жыл бұрын
why does both an if and a while loop work for the solution, for shifting the left pointer?
@pritampawar64782 жыл бұрын
great explanation easy to follow 🔥🔥🔥🔥
@EranM4 ай бұрын
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.
@vibhushajain63632 жыл бұрын
awesome explanation. thanks!
@atharvakulkarni30072 жыл бұрын
Awesome explanation loved it 😁
@tomonkysinatree4 ай бұрын
I think the easiest way to think about the maxf optimization is this: the res (length) is not updated unless the condition len - maxf
@anu89282 жыл бұрын
Amazing explanation🙏🏼
@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.
@LunaFlahy Жыл бұрын
Very smart! I think Rolling hash is an efficient way to save time optimization!
@rohandevaki43492 жыл бұрын
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
@pabloarkadiuszkalemba7415 Жыл бұрын
Another way of doing it is mantaining a max heap to get the max value, so it would be O(log(26))
@rajeshdas2295 Жыл бұрын
Nice Explanation!!!
@justforfun46803 ай бұрын
How I understood maxf is that: Only if you can get a bigger maxf (under constraint of window_length - maxf
@ritwik1213 жыл бұрын
your video saved me. thanks a lot
@rsKayiira Жыл бұрын
Excellent explanation!!
@abhiramchowdary51212 жыл бұрын
To help others who might find difficulty understanding why Maxf is not decrementing .the key is maxf is cannot be greater than maxf or count[s[r]] in the existing window .the rough explanation is unless the s[r] & s[r+1] are equal, Maxf will not increase ,if both are different you will get wrong res for that window but still it happens in previous window so we can ignore , if you might worry s[r] and s[r+1] are different but we still get Maxf same no problem since it will also give the same count. You might also worry in another case s[r] and s[r+1] are different and s[r] and s[r+2] are same , then Maxf might increase but thanks to decrement in while loop count[s[r]] will decrease and maxf will still be same.
@bibiworm9 ай бұрын
I honestly do not understand what you talked about.
@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?
@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.
@pallisaiprasad618 Жыл бұрын
Thanks for the explanation. Quick question: How is the time complexity O(n)? The while loop inside, is that considered constant time complexity?
@EquinoXReZ Жыл бұрын
Did you figure this out? Also confused about this
@mgik3503 ай бұрын
Hey, I might be a bit late but if it helps. Basically time complexity of O(n) means that with the number of operands increasing, time complexity will increase linearly. So basically if we had like 5 operands, the time complexity would be x operations, but then if we had 6 operands, the time complexity would be x + (some constant) and so on and so on. The same applies to the while loop, where for the given amount of operands the while loop will perform the same amount of iterations corresponding to the number of operands. And in the end we would still have the O(n) time complexity because of that.
@sukinkumar70422 жыл бұрын
Incredible. Especially the piece of math from 13:53! Too good :)
@legendsmnd11 ай бұрын
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.
@karlshtolz1066 Жыл бұрын
Thank You) this answer help me on ProgrammingCup
@Joyddep3 жыл бұрын
Thank you very much!
@lokeswaranaruljothy8100 Жыл бұрын
Finally, I was not the only one who don't know the last approach, even neetcode does not know about it🤣
@cindysu2622 жыл бұрын
Thank you for all your great videos, just wondering where can we access the leet code 75 Questions spreadsheet ?
@NeetCode2 жыл бұрын
No problem! I'm on my phone rn but it should be in the description of this video kzbin.info/www/bejne/iYfZo2aQn9mdf5o
@Mohib36 ай бұрын
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.
@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
@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.
@aniketbhanderi5927 Жыл бұрын
We can use int[] array of size 26 to reduce the space complexity hashmap from O(n) to O(26)=O(1). Surprisingly, it takes much less time too.
@rajkumarkhatri8119 Жыл бұрын
Because we can have no more than 26 keys in the hashmap, space complexity of hashmap (in this case) is O(26)~O(1).
@EE123456 ай бұрын
Hey, do you guys think the O(26N) to O(N) optimization would actually make the difference in an interview? To me the whole idea that we can ignore maxf while shrinking the window is hard to understand and especially to deduce in an interview setting.
@andrepinto78952 жыл бұрын
small optimization: you don't need to iterate till the last position of s. you can stop when l+res >= len(s)
@jhuang6264 Жыл бұрын
But l+res >= len(s) will only hold when the right pointer is at len(s). That's the only way you can find the best result, and by then, you would need to move L to its final position as is shown in the video before l+res >= len(s) is true.
@u2bacount2 жыл бұрын
For anyone still struggling to grasp the final optimization with maxf, I think the following can help understand. The algorithm satisfies the following 2 invariants: 1. line 10 updates maxf ito be the maximum frequency observed in the substring between l and r up until that point. 2. at line 16, the number of characters between l and r (which r - l + 1) is never greater than the longest legal substring seen up until that point
@u2bacount2 жыл бұрын
To make this point clearer, there is no point in updating res at line 16 as the result is completely determined by maxf. Here is an additional optimization which instead of updating res on every iteration of the while loop just derives the result from maxf class Solution: def characterReplacement(self, s: str, k: int) -> int: count = {} l = 0 maxf = 0 for r in range(len(s)): count[s[r]] = 1 + count.get(s[r], 0) maxf = max(maxf, count[s[r]]) while (r - l + 1) - maxf > k: count[s[l]] -= 1 l += 1 return min(maxf + k, len(s))