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
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.
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.
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.
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
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.
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
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!
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.
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 :)
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.
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.
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.
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.
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.
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.
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
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!
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.
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)
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))
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.
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.
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!!
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!
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 👍
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.
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.
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
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.
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.
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.
In the while block ( that can just be changed to if ), we can just do "continue" at the end of the block. That window would be invalid, we move left...so no need to check new max..
great, useful videos! just a small thing in this video - it was mentioned there are n squared substrings - which isn't the case - the complexity would be n squared if we checked all substrings but the number os substrings is not n squared.
I think replacing "while" with "if" would be more appropriate: while(windowLen - maxF) -> if(windowLen - maxF). For example, if the max length is currently 4 and we add one element, making the length 5, which does not satisfy the condition. At this point, the initial problem becomes "finding a subarray of length 5 that is valid." We slide the window (remove 1, add 1) to examine the next window of length 5, sliding until some window of length 5 satisfies the condition. Then we revert to the original problem of "finding the longest valid subarray", expanding the window to examine windows of length 6...
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?
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?"
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.
That optimization worked because when you use the max() function, it sorts through the array and then picks the last element. So nlog(n) for sorting every time the while iterates, and this whole thing is inside a for loop. It's pretty atrocious.
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.
I found a more elegant solution in leetcode and ez to understand also ``` Map charCount=new HashMap(); int largestCount=0,beg=0,maxlen=0; for(int end=0;end k){ //windowSize -largestCount gives us that element no which need to be change to getmaxans char startChar = s.charAt(beg); charCount.put(startChar, charCount.get(startChar) - 1); beg++; } windowSize=end-beg+1;
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.
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 ?
Consider AABAABBC. If k is 2 and we have a current window AABAAB of size 6, A has maxF of 4. Result is 6 currently. Next we shift our r pointer and window becomes 7, now number of letters to replace in window is 3 which is > k, so we increment l, window size becomes 6 and maxF technically becomes 3. By not updating maxF, we are missing on entering the while loop and reducing the window size. Since we are just missing on REDUCING the result when we already have a result thanks to the original maxF, it is ok to miss it. If suppose the original string was AABAABBBB, the first result window would be AABAAB, and then the window would keep extending right ways until it becomes AABAABBBB, when maxF is 5 thanks to B. So this is when we start reducing window from the left and excluding the As
We can refine the code for clarity and efficiency without changing its time complexity. Below are some improvements: 1)Use a defaultdict from the collections module for cleaner code. Use is it initializes a dictionary that returns 0 for missing keys by default, simplifying the code for updating character counts. 2)Maintain the maximum frequency of any character in the current window. This avoids recalculating the maximum frequency within the sliding window repeatedly, thus improving efficiency. Code Snippet with comments Below with Test Example: from collections import defaultdict class Solution: def characterReplacement(self, s: str, k: int) -> int: # Initialize the left pointer of the sliding window l = 0
# Dictionary to count the frequency of characters in the current window counts = defaultdict(int)
# Variable to keep track of the highest frequency of any single character in the current window max_freq = 0
# Variable to keep track of the length of the longest valid substring found so far longest = 0
# Iterate over the string with the right pointer of the sliding window for r in range(len(s)): # Increment the count of the current character in the window counts[s[r]] += 1
# Update the maximum frequency of any character in the current window max_freq = max(max_freq, counts[s[r]])
# Check if the current window is valid if (r - l + 1) - max_freq > k: # If the window is not valid, decrement the count of the character at the left pointer counts[s[l]] -= 1
# Move the left pointer to the right to shrink the window l += 1
# Update the length of the longest valid substring longest = max(longest, r - l + 1)
# Return the length of the longest valid substring found return longest def main(): # Create an instance of the Solution class solution = Solution()
# Test case 1 s1 = "ABAB" k1 = 2 print(f"Test case 1: s = {s1}, k = {k1} -> Output: {solution.characterReplacement(s1, k1)}")
# Test case 2 s2 = "AABABBA" k2 = 1 print(f"Test case 2: s = {s2}, k = {k2} -> Output: {solution.characterReplacement(s2, k2)}") # Ensure that the main function is called only when the script is executed directly if __name__ == "__main__": main()
One thing I still don't understand after watching this video is why this problem is a Medium problem. Shouldn't this be Hard? (Anyway, thank you for your explanation!)
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
🚀 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
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.
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!
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
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...
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.
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.
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
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.
You're the best out there - thank you for everything!
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
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!
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.
After listening to your second solution, I coded it before looking at your code, and got completely same one. Kind of proud about it!
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.
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.
The optimization with maxf is so freaking genius! Thanks for taking time to make this. Grateful🙏
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.
Loved the second approach.. Optimized Channel - No complexity in finding good videos .. this defines NeetCode
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.
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
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.
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.
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.
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
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 ♥
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!
Finally someone who explains why we didn't need to decrease the max_frequency, other videos offer no explanation.
Well explained!
The O(n) solution was really tricky.
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.
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
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)
This approach is far more superior than any other solution.
Another way of doing it is mantaining a max heap to get the max value, so it would be O(log(26))
I love the way you explain and even teaching DSA with python. Loved it TY
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.
I think the easiest way to think about the maxf optimization is this: the res (length) is not updated unless the condition len - 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.
the best of the best. I'm learning a lot from you. Huge credit to you my guy!
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.
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!!
How I understood maxf is that: Only if you can get a bigger maxf (under constraint of window_length - maxf
Awesome as always !! Love to watch your videos ! Please do the system design videos as you're very good in explaining concepts :)
How did I not find this channel earlier. youe explainations are amazing. it becomes so easy to understand.
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).
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!
This problem is tricky to get right. Thanks for the video Neetcode!
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 .
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 👍
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.
He gave the best explanation. really good man!! This channel will grow a lot in future.
The first approach was very easy to understand, thank you so much
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.
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
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
small optimization: you don't need to iterate till the last position of s. you can stop when l+res >= len(s)
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.
Damn this is the best explanation of this problem so far. Thanks for this awesome video!
Happy it's helpful! 🙂
Great explanation.Just that we don't need while over there and "if" should work fine .
It is really tricky to understand why decrementing max frequency is not important. 😕
Absolutely love your teaching style
Thanks :)
To comeup with the condition was really difficult.Thanks a ton for the awesome explanation.
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.
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.
In the while block ( that can just be changed to if ), we can just do "continue" at the end of the block.
That window would be invalid, we move left...so no need to check new max..
great, useful videos! just a small thing in this video - it was mentioned there are n squared substrings - which isn't the case - the complexity would be n squared if we checked all substrings but the number os substrings is not n squared.
number of substring will be (n+1)C2
@@Xp-Samthat is still n square
Very smart! I think Rolling hash is an efficient way to save time optimization!
bruhh,, you make this difficult questions seems so easy, thank you!
I think replacing "while" with "if" would be more appropriate: while(windowLen - maxF) -> if(windowLen - maxF).
For example, if the max length is currently 4 and we add one element, making the length 5, which does not satisfy the condition. At this point, the initial problem becomes "finding a subarray of length 5 that is valid." We slide the window (remove 1, add 1) to examine the next window of length 5, sliding until some window of length 5 satisfies the condition. Then we revert to the original problem of "finding the longest valid subarray", expanding the window to examine windows of length 6...
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?
wow this is a hard problem. i got 11/41 test cases on my own. never would have guessed the solution.
It's like I wake up and my day starts with NeetCode's voice "hey everyone, let's write some more NeetCode Today". Jokes aside, thank you.
another great day, with another great neetcode video
i was stuck at that mostf thing for 1 whole day.... thanks for adressing and explaining it
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 is so beautifully explained !! and very clever problem (Y)
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.
wow, such an elegant solution, thanks for explanation!
18:00 you have to use while there. if does not work when k=0. found it out the hard way lol
CPP solution:
Technique used: (Sliding Window - Two Pointers )
O(n) time, O(k) space
class Solution {
public:
int characterReplacement(string s, int k) {
int count[26] = {0};
int maxcount = 0;
int maxlength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
count[s.at(right) - 'A'] += 1;
maxcount = max(maxcount, count[s.at(right) - 'A']);
while(right - left + 1 - maxcount > k){
count[s.at(left) - 'A']-=1;
left++;
}
maxlength = max(maxlength, right - left + 1);
}
return maxlength;
}
};
That optimization worked because when you use the max() function, it sorts through the array and then picks the last element. So nlog(n) for sorting every time the while iterates, and this whole thing is inside a for loop. It's pretty atrocious.
This is what we call a G.O.A.T explanation !!!!!!
Wow this took me so long to understand, thank you
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.
Thank you for creating this channel.
thanks for going deep on the O(1n) case, very interesting
I found a more elegant solution in leetcode and ez to understand also
```
Map charCount=new HashMap();
int largestCount=0,beg=0,maxlen=0;
for(int end=0;end k){ //windowSize -largestCount gives us that element no which need to be change to getmaxans
char startChar = s.charAt(beg);
charCount.put(startChar, charCount.get(startChar) - 1);
beg++;
}
windowSize=end-beg+1;
maxlen=Math.max(maxlen,windowSize);
}
return maxlen;
```
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.
you can acutally just return j-i at the end instead of holding result since result never decreases
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?
Consider AABAABBC. If k is 2 and we have a current window AABAAB of size 6, A has maxF of 4. Result is 6 currently. Next we shift our r pointer and window becomes 7, now number of letters to replace in window is 3 which is > k, so we increment l, window size becomes 6 and maxF technically becomes 3. By not updating maxF, we are missing on entering the while loop and reducing the window size. Since we are just missing on REDUCING the result when we already have a result thanks to the original maxF, it is ok to miss it. If suppose the original string was AABAABBBB, the first result window would be AABAAB, and then the window would keep extending right ways until it becomes AABAABBBB, when maxF is 5 thanks to B. So this is when we start reducing window from the left and excluding the As
Thanks for such a nice and clear explanation!!
We can refine the code for clarity and efficiency without changing its time complexity. Below are some improvements:
1)Use a defaultdict from the collections module for cleaner code. Use is it initializes a dictionary that returns 0 for missing keys by default, simplifying the code for updating character counts.
2)Maintain the maximum frequency of any character in the current window. This avoids recalculating the maximum frequency within the sliding window repeatedly, thus improving efficiency.
Code Snippet with comments Below with Test Example:
from collections import defaultdict
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
# Initialize the left pointer of the sliding window
l = 0
# Dictionary to count the frequency of characters in the current window
counts = defaultdict(int)
# Variable to keep track of the highest frequency of any single character in the current window
max_freq = 0
# Variable to keep track of the length of the longest valid substring found so far
longest = 0
# Iterate over the string with the right pointer of the sliding window
for r in range(len(s)):
# Increment the count of the current character in the window
counts[s[r]] += 1
# Update the maximum frequency of any character in the current window
max_freq = max(max_freq, counts[s[r]])
# Check if the current window is valid
if (r - l + 1) - max_freq > k:
# If the window is not valid, decrement the count of the character at the left pointer
counts[s[l]] -= 1
# Move the left pointer to the right to shrink the window
l += 1
# Update the length of the longest valid substring
longest = max(longest, r - l + 1)
# Return the length of the longest valid substring found
return longest
def main():
# Create an instance of the Solution class
solution = Solution()
# Test case 1
s1 = "ABAB"
k1 = 2
print(f"Test case 1: s = {s1}, k = {k1} -> Output: {solution.characterReplacement(s1, k1)}")
# Test case 2
s2 = "AABABBA"
k2 = 1
print(f"Test case 2: s = {s2}, k = {k2} -> Output: {solution.characterReplacement(s2, k2)}")
# Ensure that the main function is called only when the script is executed directly
if __name__ == "__main__":
main()
One thing I still don't understand after watching this video is why this problem is a Medium problem. Shouldn't this be Hard?
(Anyway, thank you for your explanation!)
Great job mate, very good explanation... keep working, your channel will definitely grow. It's the best
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
Finally, I was not the only one who don't know the last approach, even neetcode does not know about it🤣
Hey, just want to say that you're the best :D Your visualization makes a lot of difference. Thank you!
I have understood only your explanation of this problem, thank!