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.
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
@@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
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.
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."
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
Right, as the question doesn't really specify the first or the last longest substring, hence it doesn't really matter as long as the substring is the largest. Our code will always likely give us the last longest substring even if a 'longest' substring of that length was already found at an earlier stage.
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.
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!
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.
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.
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
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.
Here is how I understood the optimized solution: The problem with not shrinking maxf is that, it is possible to consider an invalid substring which needs k+1 replacements as a valid substring. And if our result comes from the length of an invalid substring we're doomed. But the lucky thing is, when we need to shrink the sliding window and shrink maxf, our most recent result must be the substring that barely satisfied the constraint "length
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.
@@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.
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!
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.
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!
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 :)
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.
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))
@@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.
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
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.
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.
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.
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.
3:38 "We want all characters in window to match most common character". I struggled to believe this greedy strategy gives the best answer, and came up with a counter-example BCDBCDBAZA and k=1. In this case B is most common with 3 but using the k on A gives the best answer of 3 instead of 2 if used for B. Then I realized this example would be an impossible window if we followed the sliding window technique which would have long ago moved the left pointer. Lesson is to trace through an example in more detail by actually following through an iteration strategy, instead of jumping into the middle of some loop and checking scenarios, and the fact that there's a chicken-egg issue. Before coming up with solution, we need test cases, but the test cases are influenced by iteration strategy. Here's a case of using impossible test cases that makes finding solution impossible. If someone does not know sliding window, it would be very difficult to even know that BCDBCDBAZA is a bad example. How do others deal with this "wrong test case leading to false negative strategy" situation? Are there better answers than "Memorize every solution strategy, throw all and see what sticks?"
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?
I was keeping track of the frequent character and based on that was updating an internal K value along with max frequency. But that made the code too complex, had to handle lot of cases. But when I saw your solution, I couldn't believe how simple you made it.
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!!
The maxf is so tricky - but its one of the tricks I can genuinely appreciate. It requires us to really understand the fundamental logic of this problem for it to even be a thought in our heads
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.
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)
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.
For this problem, the solution suggests, use two-pointer method to make sure the substring is valid. The condition for that is (right-left+1) - max(count.values()) > k. And the examples provided only show two characters. What happens if there are more than 2 characters ? If we even replace the maximum occurring character, what is the guarantee the remaining characters are all the same? Attaching the code which is passing . class Solution: def characterReplacement(self, s: str, k: int) -> int: count = {} left = 0 res = 0 for right in range(len(s)): count[s[right]] = count.get(s[right],0)+1 while right-left+1 - max(count.values()) > k: count[s[left]] -= 1 left += 1 res = max(res,right-left+1) return res
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
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))
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.
If we enter the while condition and move our left part, we will decrease count[s[left]]. What if s[left] is the most frequent char ? Shouldn't maxf be updated too ? Because in the iteration after that, we would compare the old maxf (which counts some char that have been cut off the window) with count[right] and assign the max of that to maxf. Woulnd't that overestimate maxf ?
Not only is the if statement sufficient, it is more efficient. If you used the while loop, you would be incrementing left, but keeping right static and therefore never finding a window longer than the longest already found. However if you did the if statement you're never doing unnecessary operations on smaller sized windows, and will reach the end condition of the for loop faster.
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.
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.
great video! I think it makes sense though to use an "if" condition instead of the "while" loop because you are checking that condition twice unnecessarily. once you move that left pointer over once, you will always break while loop because (r - l - 1) - maxf > k will return false. def characterReplacement(self, s, k): count = {} if k+1 >= len(s): return len(s) l = 0 r = 0 maxcount = 0 while r < len(s): count[s[r]] = 1 + count.get(s[r], 0) maxcount = max(maxcount, count[s[r]]) if (r-l+1) - maxcount > k: count[s[l]] -= 1 l += 1 r += 1 return r-l
I don't understand at all why the "res = max(res, r-l +1)" happens on every iteration. If we have the example AABAB where k=1, A works, AA works, AAB works, AABA works, but AABAB doesn't work, so we reduce the window and now the A on the left disappears and we have _ABAB. According to this code, we update the result to now be 4, but "ABAB" is not a valid window. I'm so confused...
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! :-)
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.
once you start shrinking the window, the max count is no longer the max within the window, but a somewhat global max in the whole substring that you have scanned so far, this count is all screwed up, isn't it? I still don't get it.
Maybe since you are only shifting the left pointer while the right pointer is fixed, the new max count will not exceed the previous one, and the res will not change as well when you shrink the sliding window. I wrote a similar solution which might make it clearer :) class Solution: def characterReplacement(self, s: str, k: int) -> int: l = 0 res = 0 cnt = {} maxf = 0 for r in range(len(s)): cnt[s[r]] = 1 + cnt.get(s[r], 0) maxf = max(maxf, cnt[s[r]]) if r-l+1 - maxf k: cnt[s[l]] -= 1 l += 1 return res
Needless to update maxf when l increase and (r - l + 1) decrease, ((r - l + 1) - maxf) will stay the same if s[l] is the character of max frequency, ((r - l + 1) - maxf) will decrease when s[l] is not character of max frequency or just one of characters of max frequency.
Plus, there's a room you can improve the logic a little bit. instead of max(count.values()), you may define a variable, let's say 'currentMax' then you can replace max(count.value()) with max(count[s[r]], currentMax). Then, it doesn't need to iterate all the values, instead it compares only two values. Thanks for the video neetcode 👍
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
hi Neetcode In you Website Code Submission isn't auto Updating we need to refresh inoreder to get the latest submission
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.
Also for interviewees, its good to talk this through out loud in an interview so they can see your thought process!
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
probably the best possible breakdown. thank you, jeremy.
he said same thing at 14:00
"the main idea is this ..."
@@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
@@TaikiTanaka-n6cI agree. The wording here is better!
@neetcode needs to pin this comment.
Please keep doing this for more Leetcode problems - nobody explains them like you do. This channel deserves so many more subscribers!
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.
Great insight. The while loop was unnecessary all along and just overcomplicated both the overall solution and the maxf optimisation.
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
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."
Good point
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.
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
Right, as the question doesn't really specify the first or the last longest substring, hence it doesn't really matter as long as the substring is the largest. Our code will always likely give us the last longest substring even if a 'longest' substring of that length was already found at an earlier stage.
it's not easy to get one's head around this one, thanks for working it through!💚
True, thanks @Neetcode that slow explanation really helped my brain
yeah this one is tough to think about.
You're the best out there - thank you for everything!
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.
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!
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.
thank you, that's exactly what i was looking for in comments, i did wonder why my if statement worked actually
thank you
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.
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
thanks you🥰@@fujiantao7680
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.
After listening to your second solution, I coded it before looking at your code, and got completely same one. Kind of proud about it!
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...
the best of the best. I'm learning a lot from you. Huge credit to you my guy!
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
This doesn't work when s='ABAA' k=0, the result should be 2 but you will get 1
nah, won't work in every case.
Here is how I understood the optimized solution:
The problem with not shrinking maxf is that, it is possible to consider an invalid substring which needs k+1 replacements as a valid substring. And if our result comes from the length of an invalid substring we're doomed.
But the lucky thing is, when we need to shrink the sliding window and shrink maxf, our most recent result must be the substring that barely satisfied the constraint "length
thanks man ❤❤🫡
My personal notes on why the O(n) solution works:
This is our equation: length - maxFreq
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.
@@qwertyasdf6301 I have the same question, did you figure out why not updating maxf doesn't mess up the window manipulations?
@@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.
@@h3ckphy246 "Personally I tried this string: AAABBCCDAA." And what is your value of k for this example ? I will try it out.
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!
Loved the second approach.. Optimized Channel - No complexity in finding good videos .. this defines NeetCode
Well explained!
The O(n) solution was really tricky.
The optimization with maxf is so freaking genius! Thanks for taking time to make this. Grateful🙏
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.
We can use array to hold frequency as string is only consist of uppercase english letters.
I love the way you explain and even teaching DSA with python. Loved it TY
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!
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 :)
general solution is always likely infinite times better.
He gave the best explanation. really good man!! This channel will grow a lot in future.
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 ♥
Amazing video! Note that you can simply do: res = r - l + 1 without using max, and still get the correct answer (with fewer operations).
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.
this one is hard
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))
@@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.
@@yuurishibuya4797 isn’t better to understand the different solutions and patterns and then try to apply those yourself on similar problems?
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
How did I not find this channel earlier. youe explainations are amazing. it becomes so easy to understand.
Best explanation I have seen so far on this topic! great job
Awesome as always !! Love to watch your videos ! Please do the system design videos as you're very good in explaining concepts :)
Damn this is the best explanation of this problem so far. Thanks for this awesome video!
Happy it's helpful! 🙂
The first approach was very easy to understand, thank you so much
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.
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
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.
@@mihirmodi1936 Why? Please tell me.
@@InfinityOver0 It works with if, because we anyways will iterate to the next j pointer and check the condition for k
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.
This should be a leetcode hard. This is way harder than the water trap question.
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
This approach is far more superior than any other solution.
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.
Finally someone who explains why we didn't need to decrease the max_frequency, other videos offer no explanation.
3:38 "We want all characters in window to match most common character".
I struggled to believe this greedy strategy gives the best answer, and came up with a counter-example BCDBCDBAZA and k=1.
In this case B is most common with 3 but using the k on A gives the best answer of 3 instead of 2 if used for B.
Then I realized this example would be an impossible window if we followed the sliding window technique which would have long ago moved the left pointer.
Lesson is to trace through an example in more detail by actually following through an iteration strategy, instead of jumping into the middle of some loop and checking scenarios, and the fact that there's a chicken-egg issue.
Before coming up with solution, we need test cases, but the test cases are influenced by iteration strategy.
Here's a case of using impossible test cases that makes finding solution impossible. If someone does not know sliding window, it would be very difficult to even know that BCDBCDBAZA is a bad example.
How do others deal with this "wrong test case leading to false negative strategy" situation? Are there better answers than "Memorize every solution strategy, throw all and see what sticks?"
This problem is tricky to get right. Thanks for the video Neetcode!
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?
I was keeping track of the frequent character and based on that was updating an internal K value along with max frequency. But that made the code too complex, had to handle lot of cases. But when I saw your solution, I couldn't believe how simple you made it.
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!!
The maxf is so tricky - but its one of the tricks I can genuinely appreciate. It requires us to really understand the fundamental logic of this problem for it to even be a thought in our heads
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.
Great job mate, very good explanation... keep working, your channel will definitely grow. It's the best
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)
Absolutely love your teaching style
Thanks :)
Thanks for the explanation.
Quick question: How is the time complexity O(n)?
The while loop inside, is that considered constant time complexity?
Did you figure this out? Also confused about this
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.
For this problem, the solution suggests, use two-pointer method to make sure the substring is valid.
The condition for that is (right-left+1) - max(count.values()) > k.
And the examples provided only show two characters.
What happens if there are more than 2 characters ? If we even replace the maximum occurring character, what is the guarantee the remaining characters are all the same? Attaching the code which is passing .
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = {}
left = 0
res = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right],0)+1
while right-left+1 - max(count.values()) > k:
count[s[left]] -= 1
left += 1
res = max(res,right-left+1)
return res
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
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))
Thanks! This finally clicked after reading a bunch of different responses.
You're doing an awesome job!! Thank you! Keep up the work, you're helping a lot of us!
bruhh,, you make this difficult questions seems so easy, thank you!
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 .
Incredible. Especially the piece of math from 13:53! Too good :)
To comeup with the condition was really difficult.Thanks a ton for the awesome explanation.
Another way of doing it is mantaining a max heap to get the max value, so it would be O(log(26))
Sliding window is one of the most essential algorithm someone can learn!
Hey, just want to say that you're the best :D Your visualization makes a lot of difference. Thank you!
another great day, with another great neetcode video
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.
I honestly do not understand what you talked about.
If we enter the while condition and move our left part, we will decrease count[s[left]]. What if s[left] is the most frequent char ? Shouldn't maxf be updated too ? Because in the iteration after that, we would compare the old maxf (which counts some char that have been cut off the window) with count[right] and assign the max of that to maxf. Woulnd't that overestimate maxf ?
did anyone got this?
18:00 you have to use while there. if does not work when k=0. found it out the hard way lol
Not only is the if statement sufficient, it is more efficient. If you used the while loop, you would be incrementing left, but keeping right static and therefore never finding a window longer than the longest already found. However if you did the if statement you're never doing unnecessary operations on smaller sized windows, and will reach the end condition of the for loop faster.
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.
The explanation is really good, easy to follow and understand.
How I understood maxf is that: Only if you can get a bigger maxf (under constraint of window_length - maxf
I think the easiest way to think about the maxf optimization is this: the res (length) is not updated unless the condition len - maxf
Thanks for such a nice and clear explanation!!
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.
Wow this took me so long to understand, thank you
Wonderful solution!! Keep making videos! You will definitely get more subscribers!!
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.
Because we can have no more than 26 keys in the hashmap, space complexity of hashmap (in this case) is O(26)~O(1).
great video! I think it makes sense though to use an "if" condition instead of the "while" loop because you are checking that condition twice unnecessarily. once you move that left pointer over once, you will always break while loop because (r - l - 1) - maxf > k will return false.
def characterReplacement(self, s, k):
count = {}
if k+1 >= len(s):
return len(s)
l = 0
r = 0
maxcount = 0
while r < len(s):
count[s[r]] = 1 + count.get(s[r], 0)
maxcount = max(maxcount, count[s[r]])
if (r-l+1) - maxcount > k:
count[s[l]] -= 1
l += 1
r += 1
return r-l
This is so beautifully explained !! and very clever problem (Y)
Thank you for creating this channel.
Absolutely clean explanation, good work!
wow, such an elegant solution, thanks for explanation!
I don't understand at all why the "res = max(res, r-l +1)" happens on every iteration. If we have the example AABAB where k=1, A works, AA works, AAB works, AABA works, but AABAB doesn't work, so we reduce the window and now the A on the left disappears and we have _ABAB. According to this code, we update the result to now be 4, but "ABAB" is not a valid window. I'm so confused...
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! :-)
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.
This is what we call a G.O.A.T explanation !!!!!!
How is the first solution O(26n)? Summing up n + (n-1) + (n-2) + ... should still be O(n^2)?
Dude, you are awesome. Thanks for your clean explanation.
why does both an if and a while loop work for the solution, for shifting the left pointer?
Thanks a lot for your explanation. I was so curious about solving in more efficient than O(26*n).
once you start shrinking the window, the max count is no longer the max within the window, but a somewhat global max in the whole substring that you have scanned so far, this count is all screwed up, isn't it? I still don't get it.
hmm yea that is the part that I don't understand either lol, how does maxf stay constant when we do the check in the while loop lmao
Maybe since you are only shifting the left pointer while the right pointer is fixed, the new max count will not exceed the previous one, and the res will not change as well when you shrink the sliding window. I wrote a similar solution which might make it clearer :)
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
l = 0
res = 0
cnt = {}
maxf = 0
for r in range(len(s)):
cnt[s[r]] = 1 + cnt.get(s[r], 0)
maxf = max(maxf, cnt[s[r]])
if r-l+1 - maxf k:
cnt[s[l]] -= 1
l += 1
return res
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
l=0
r=0
maxi=0
ans=0
temp=0
n=len(s)
hm={}
while(rk:
#shrinking the window and decreasing most frequent character
hm[s[l]]-=1
l+=1
ans=max(ans,r-l+1)
r+=1
return ans
thanks for going deep on the O(1n) case, very interesting
Needless to update maxf when l increase and (r - l + 1) decrease, ((r - l + 1) - maxf) will stay the same if s[l] is the character of max frequency, ((r - l + 1) - maxf) will decrease when s[l] is not character of max frequency or just one of characters of max frequency.
Thanks!
how do you come up with solutions. i try for hours and then maybe get a naive solution which probably gets time limit exceed error
Plus, there's a room you can improve the logic a little bit. instead of max(count.values()), you may define a variable, let's say 'currentMax' then you can replace max(count.value()) with max(count[s[r]], currentMax). Then, it doesn't need to iterate all the values, instead it compares only two values. Thanks for the video neetcode 👍