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.
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.
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.
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.
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!
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.
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.
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.
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 :)
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.
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!
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
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.
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.
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.
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.
Use max heap to save the biggest character :> You can also save a map for the nodes in the heap for easier "increase/decrease key" operations. Any priority queue will suffice.
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.
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?
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!)
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)
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...
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 ?
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.
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.
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
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 👍
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
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))
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...
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.
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.
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.
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!!
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;
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()
In the solution on the site, you just return the window length and don't track the max length the way you do with res = max(res, r - l + 1). Why does it work? Like, why is the length of "current" window when we've finished iterating through the string going to be the longest window as well?
Is it a Google Second Time Coding Interview level question? If it is. If I walk through the first solution with the interviewer. Can I get a Hire or Strong Hire? Thank you.
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
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..
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.
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.
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.
Can someone explain this to me: If the current substring is invalid we move the left pointer by 1. It turns out that if change the logic to: move both the pointers by 1 to the right when an invalid substring is encountered, it still works and is a little bit faster. So if L-R is invalid NC approach is to consider L+1 & R, if instead we jump to L+1 & R+1, the algorithm is a little bit faster and still correct. Why can we skip considering L+1 & R and instead focus on L+1 & R+1? class Solution: def characterReplacement(self, s: str, k: int) -> int: if len(s) == 1: return 1 max_len = 0 required_edits = 0 l = 0 r = 1 count_dict = {s[l]:1} max_count = 1; ref_char = s[0] while r < len(s): count_dict[s[r]] = 1 + count_dict.get(s[r],0) required_edits = r+1-l - max(count_dict.values()) #len(s[l:r+1]) is r-l+1 if required_edits
Regarding not downgrading maxFreq: How about (K = 2) AAAABA where maxFreq = 5 for A and max result = 6 (5 + 1 replacement of B) followed by CCCCDDD where maxFreq = 4 for C and max result = 6 too (4 + 2 replacements of D), where the last D should be excluded. However, length = 7 and non-downgraded maxFreq = 5 passes the condition length - maxFreq = 2
I assume you mean if we combine those two strings together to make "AAAABACCCCDDD" in which case the string "AAAABAC" would be length 7 and require only 2 replacements which is valid
🚀 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
@@user-nj1xh8ot3fI 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!
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...
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
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!
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.
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.
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.
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.
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!
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.
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.
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.
the best of the best. I'm learning a lot from you. Huge credit to you my guy!
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.
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.
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!
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
The optimization with maxf is so freaking genius! Thanks for taking time to make this. Grateful🙏
After listening to your second solution, I coded it before looking at your code, and got completely same one. Kind of proud about it!
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.
Loved the second approach.. Optimized Channel - No complexity in finding good videos .. this defines NeetCode
Awesome as always !! Love to watch your videos ! Please do the system design videos as you're very good in explaining concepts :)
Well explained!
The O(n) solution was really tricky.
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 ♥
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.
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.
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.
I think the easiest way to think about the maxf optimization is this: the res (length) is not updated unless the condition len - maxf
Use max heap to save the biggest character :>
You can also save a map for the nodes in the heap for easier "increase/decrease key" operations.
Any priority queue will suffice.
Damn this is the best explanation of this problem so far. Thanks for this awesome video!
Happy it's helpful! 🙂
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.
How I understood maxf is that: Only if you can get a bigger maxf (under constraint of window_length - maxf
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
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?
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!)
Jesus fu*king christ how M I supposed to solve these problems in an interview
🤣🤣🤣
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.
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...
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?
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 love the way you explain and even teaching DSA with python. Loved it TY
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.
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
The first approach was very easy to understand, thank you so much
Finally someone who explains why we didn't need to decrease the max_frequency, other videos offer no explanation.
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!
It is really tricky to understand why decrementing max frequency is not important. 😕
bruhh,, you make this difficult questions seems so easy, thank you!
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 👍
He gave the best explanation. really good man!! This channel will grow a lot in future.
Another way of doing it is mantaining a max heap to get the max value, so it would be O(log(26))
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).
Absolutely love your teaching style
Thanks :)
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.
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 .
Finally, I was not the only one who don't know the last approach, even neetcode does not know about it🤣
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
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;
}
};
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))
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...
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.
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.
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
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.
To comeup with the condition was really difficult.Thanks a ton for the awesome explanation.
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!!
another great day, with another great neetcode video
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;
```
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()
In the solution on the site, you just return the window length and don't track the max length the way you do with res = max(res, r - l + 1). Why does it work? Like, why is the length of "current" window when we've finished iterating through the string going to be the longest window as well?
wow this is a hard problem. i got 11/41 test cases on my own. never would have guessed the solution.
It’s pretty easy when you realize you don’t need the current max, but the all time max
Wow this took me so long to understand, thank you
Is it a Google Second Time Coding Interview level question? If it is. If I walk through the first solution with the interviewer. Can I get a Hire or Strong Hire? Thank you.
Thanks for such a nice and clear explanation!!
How does one come up with this optimal solution without having seen this problem before?!
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
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.
How is the first solution O(26n)? Summing up n + (n-1) + (n-2) + ... should still be O(n^2)?
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
Great job mate, very good explanation... keep working, your channel will definitely grow. It's the best
i was stuck at that mostf thing for 1 whole day.... thanks for adressing and explaining it
This should be a leetcode hard. This is way harder than the water trap question.
You're doing an awesome job!! Thank you! Keep up the work, you're helping a lot of us!
Thank you for all your great videos, just wondering where can we access the leet code 75 Questions spreadsheet ?
No problem! I'm on my phone rn but it should be in the description of this video ruclips.net/video/SVvr3ZjtjI8/видео.html
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..
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.
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.
18:00 you have to use while there. if does not work when k=0. found it out the hard way lol
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.
Can someone explain this to me: If the current substring is invalid we move the left pointer by 1. It turns out that if change the logic to: move both the pointers by 1 to the right when an invalid substring is encountered, it still works and is a little bit faster.
So if L-R is invalid NC approach is to consider L+1 & R, if instead we jump to L+1 & R+1, the algorithm is a little bit faster and still correct. Why can we skip considering L+1 & R and instead focus on L+1 & R+1?
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
if len(s) == 1:
return 1
max_len = 0
required_edits = 0
l = 0
r = 1
count_dict = {s[l]:1}
max_count = 1; ref_char = s[0]
while r < len(s):
count_dict[s[r]] = 1 + count_dict.get(s[r],0)
required_edits = r+1-l - max(count_dict.values()) #len(s[l:r+1]) is r-l+1
if required_edits
Regarding not downgrading maxFreq: How about (K = 2)
AAAABA where maxFreq = 5 for A and max result = 6 (5 + 1 replacement of B)
followed by
CCCCDDD where maxFreq = 4 for C and max result = 6 too (4 + 2 replacements of D), where the last D should be excluded.
However, length = 7 and non-downgraded maxFreq = 5 passes the condition length - maxFreq = 2
I assume you mean if we combine those two strings together to make "AAAABACCCCDDD" in which case the string "AAAABAC" would be length 7 and require only 2 replacements which is valid
Walkthrough so good you'd be forgiven for already being scared of when the channel is no longer updated ;_;
Very smart! I think Rolling hash is an efficient way to save time optimization!