LeetCode Longest Repeating Character Replacement Solution Explained - Java
HTML-код
- Опубликовано: 22 авг 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
One thing that isn't well explained is that max_count keeps track of the rolling max frequency of characters from index 0 to i. It does not keep track of the maximum frequency of characters in the window, which is what "window_end - window_start - max_count + 1 > k" is checking. This works fine, but the reason this works isn't trivial and definitely deserves a better explanation.
Yes, I'm also wondering this. max_count never decreases when window_start slides to the right.
I was wondering about the same thing. The simple equation felt like black magic. So here's how I understood it. maxFreq is actually keeping count of the maxFreq(lets call this maxFreq1) of a letter seen so far. Why we need this and not the actual maxFreq1 in the rolling window you may ask? Cuz we know that with that maxFreq the window size can be maxFreq+k at min. So it doesnt really matter until you encounter another substring which has more frequency and satisfies that equation. j-i+1 - maxFreq
yea, why isnt he recalculating maxFrequency when hes sliding the window right..
Hey, Nick. Just a thought, I think the '+ 1' in these equations is to account for zero-indexing. Because 2 - 0 = 2 but array[0] + array[1] + array[2] = size of 3
Exactly right. It is not because he is adding a new letter, it is because our pointers are zero based.
I don't think it is because of the zero-indexing. From my point of view It's because we are subtracting the starting point. It's something similar with months. How many months are there from January (1) to June (6)? If we do the subtraction 6-1=5, but I'm not taking in count January, so I have to add 1 to get 6
@@zzzzzalanzzzzz Yeah, imo you're correct.
@@zzzzzalanzzzzz This has to be the dumbest explanation, it is because its arrays are zero indexed
@Alan Serrano yeah you're right. For those who might be confused, consider two arrays one with 0-indexing and other with 1-indexing, [0,1,2,3] and [1,2,3] -> in both cases 3-1 would give 2, but actually there are 3 elements.
the key to this question is why you dont update the max_count when you shrink the window. I have watched several videos now, everyone just skip that part!
Why don't you have to recalculate max_count in the while loop? what if you pop a character off of the front, which was used to calculate max_count? In your code, max_count is simply the count of the most frequently seen character across the ENTIRE STRING not the window. Actually, I think this problem on leetcode is broken. The test cases are probably very simple, so everyone can get by with wrong code. Please correct me if I'm wrong.
same doubt
You can try your own test cases, no? But in this case, max is only changed/updated if a character is added, not subtracted. If you encounter the character again that you popped off, it will check (in the main while loop) if this visit will push the max up.
I had the same thought. But it is not required because if you look closely, size of the window never decreases. You can replace while with if and it will still work.
@@itsbossable i dont understand
@@Cube2deth Consider this example "AAABCDEFG" with k=2. The algorithm will increase the window size until it reaches a length of 5. i.e. the length of "AAABC". After this, the window size will remain at 5 until and unless we get a max_count that is greater than the previous. In this case we do not encounter a max_count that is greater than 3 and therefore the max_length will remain 5 for the rest of the iterations. I would advise to trace it and see for yourself.
When you are incrementing your window_start pointer and decrementing the count of that character(and lets assume that the first character was the max count so far,) how do you ensure that the char with highest count remains same?
Am I making any sense.
yess. Have the same doubt
Because it has to be consecutive, when ur out of operation, the only thing you can do is to shrink the window size from left, and you already have the max length at this step. Since the max length will only be updated when a longer one is found, it doesn't matter if the highest freq char is the same or not.
Exactly! And the weirdest thing is nobody is mentioning this in the Leetcode discussion. I'm so confused.
@@menglishu4328 this is the most clear explanation that i found. Thank you
Simple form to understand this one
private static int findLongRepCharRepl(String s, int k) {
int[] counts_char = new int[26];
int left =0;
int max_count = 0;
int result = 0;
for(int right =0; right < s.length(); right++){
int windowSize = right - left + 1;
counts_char[s.charAt(right) - 'A'] = counts_char[s.charAt(right) - 'A'] + 1;
int current_char_count = counts_char[s.charAt(right) - 'A'];
max_count = Math.max(max_count , current_char_count);
int replace_count = windowSize - max_count;
if(replace_count > k){
counts_char[s.charAt(left) - 'A'] = counts_char[s.charAt(left) - 'A'] - 1;
left = left + 1;
}else{
result = Math.max(result,windowSize );
}
}
return result;
}
what about updating the max_count when we increment the window_start ?
no body is explaning that
doesnt matter how much questions u do at the end the way of ur explanation conveys the interviewer how much intelligent u r
And also after sliding the window why we are not updating the max_count since it might change depending on the character which corresponds to max_count.
well the inside while loop basically runs for 1 time only, so I think there is no point for updating the max_count.
that's exactly what I am thinking, if the max_count comes from window_start then we need to update the max_count to max_count - 1, isn't it ?
Thanks for the video! I think I understood, but it could help if you walked through the condition in the while loop more thoroughly. It is especially important for a test case like s = "BAAAB" and k = 2, where after we visit BAA, the max_count switches from B's count to A's count.
I was confused about this too. I think it makes more sense in the context of this approach to think of max_count as the max count of repeating characters across *all* sliding windows instead of the *current* sliding window.
While loop is used to decrease the window size and update char_count based on removed character. So, start will be incremented until we reach a point where window will become feasible again for max_count character.
Test case: s=ACBAD..........., k=2. When window_end is 4, which points to "D", we need to move window_start to the right. By following your code, window_start will be stoped at index 1, since 4 - 1 - 2 + 1 = 2 == k, but substring "CBAD" doesn't fulfill the requirement.
Here's a C++ implementation:
"""""""""""""""""""""""""""""""""""""""""""""""""
class Solution {
public:
int characterReplacement(string s, int k) {
int n = (int)s.length();
unordered_map count; // character frequencies in the sliding window
int max_length = 0; // longest consecutive substring (after operations) so far
int max_count = 0; // most frequent char occurence in the sliding window
// j: sliding window start, i: sliding window end
for (int i = 0, j = 0; i < n; ++i) { // 'i' loops through the string normally
count[s[i]]++; // update current char count
max_count = max(max_count, count[s[i]]); // whether current char has higher freq
while (i - j + 1 - max_count > k) { // compare no. of operations we must do with k
count[s[j]]--; // decrease s[j]'s freq because we gon shrink
j++; // shrink window on the left
}
max_length = max(max_length, i - j + 1);
}
return max_length;
}
};
There is some problem with the max_count. It's wrong to say the definition of it is the maximum count of same characters in the window. If it's, if the most frequent character get removed from the start, you should decrease the max_count.
However, Nick didn't, meaning it should be the maximum count of same characters occurred so far. I don't know why this implementation can work. Maybe some explanation is missing? Can anyone explain it, expecially the definition of max_count?
max count is local. it is the max count for characters between start and end. Everytime start or end changes, max count changes accordingly.
Yeah it should be max_count_so_far, answer belongs the window where this occured. That is why this implementation works.
If you consider another window w2 with max_same_char_count less than max_count_so_far, adding it with k will result in smaller substring.
We don't need to recalculate max_count because our goal is to find the substring where the max_count is maximum. The more the repeating characters in our string, the better ('aaaaab' is better than 'aab' because in the first one we have more repeating chars, therefore it's longer) . In the solution, when we move the start pointer forward and don't update the max_count, the substring gets counted as a valid substring (even if it isn't) but it doesn't matter to us because the length of this substring is smaller than the maxLength we found earlier. Try iterating through the second example test case step by step and you'll see for yourself as to why updating the max_count doesn't matter. Hope this helps!
@@neeyatiajmera869 wonderful!
@@neeyatiajmera869 How can it possibly be smaller than the maxlength we found earlier if the sliding window can only ever grow or stay the same size?
If you explain your code like you did in video, I wouldn't hire you.
Lol.
agreed, very sloppy, and impatient. he might be a good programmer if he actually knows these stuff not just memorizing it. but he would not be a good leader or mentor.
Got to recalculate max count after popping character from the front. Also, I am not sure what's the Big O order of this approach?
I had the same thought. But it is not required because if you look closely, size of the window never decreases. You can replace while with if and it will still work.
@@itsbossable thanks! Your comment helped me understand that.
@@PrasoonTelang I dont understand why?
@@Cube2deth i know its late. But replacing while with if will work because we are checking count of non repeating characters in every step and if count(of non repeating characters) >k then we immediately update start of window and k again k comes in range
@@CinghAnkit makes sense, thanks!
Great video! Just one suggestion, you can replace the 'while' with 'if', it'll still work
But why does it work ?
quick note, solution also works if you use an if statement instead of a while loop
One of the best video about this question on the internet, I got it in 1 watch.
Thanks for making it.
🧡 from remote.
Sometimes I wonder why kevin and nick don't use whiteboard and pen to explain the solution.
nice video. thanks. one thing that took some time to get my head around was this maths. (window-end - window_start + 1 - max_count) > k.. I understood by reading it as (window_length - max_count) >k .. this is what tells us to adjust start of window because maxCount is no of repeated elements in the window and length - maxCount gives no of different elements in the window which are upper bound by k. so for example AAABCDE and k of 1, at window length 5 i.e. at element C, maxCount is 3 and hence no of different elements in window is 5-3 =2 which is > 1(k). hence we need to remove start.
Hi Nick,
First of, excellent video!
I was wondering why max_count keeps count of a character that is repeated the most, even though if its not a part of sliding window?
Eg: s="aaaaabbcde"
window_start = 1
window_end = 7
sliding window at this instance= "aaaabbc"
As per our code, this will be a legal output (if we were to output string), right?
So, I thought maybe max_count should be max frequency of any character within the sliding window i.e. 'a' occurs 4 times and so, max_count should be 4.
The reason I am thinking this way is due to the fact that at each instance, we try to have a sliding window which accepts output.
Thank you,
Rohan
same doubt
if the new max count is introduced by the new idx, then with the current window it can not form a new valid substring with char at the new idx. if the max is still the same before this new idx then the max substring is covered by previous logic.
Hi Nick... This is a great video and I quite enjoyed the ending. That was cool.
haha thanks man!
The reason why he didn't have to update max_count in the while loop is because the while loop will run at most one iteration. So if that while was replaced with an "if", it still would work
Why use while loop though? the loop's not expected to run more than once, then doesn't it make more sense to just use "if"?
@@goodtoseeya1543 yes correct. try it out on leetcode.
Precisely! I replaced 'while' with 'if' and the solution got accepted. Using 'while' was resulting in 'ArrayOutOfBound' exception.
don't understand the downvotes. I find your explanation intuitive.
People thinking (as I was) that why he is not updating the value of max_count if he is deleting an element from the window front which has that count is because the length of the window is never going to be greater than max_length until max_count is increased. Hence, no need of adding extra redundant steps.
But for instance if we have a string like ABACDE, once max_count reaches to 2 (due to we have 2 A), then the rest of the computation we are always using max_count = 2, that messes everyone up, isn't it??
What mic/audio capture settings do you use? It sounds like I'm wearing headphones when you speak
Sounds recored in mono.
Hey Nick wondering if this could be solved using dp?
Thinking aloud:
If I do top down approach from i=0, then if I know the longest repeating character replacement (LRCR) for the substring starting from i+1th position then I could get the LRCR for substring starting from i under the constraint that if ith char is same as i+1th char or if the operations done are
nice and strong logic bro ...
A little easier to understand solution would be to actually convert this probelm into max consecutive ones . where one(repeating character) can be changed to any character from A to Z .
Hey Nick I am from India,plzz don't feel frustrated you explain superbly
Like you the most among all who Leetcode on RUclips. Always intuitive, quick and crystal clear.
you said subarray problems are sliding window approach, then which problems do you suggest to solve to get these kind of appraoches? and thought process?
Jumped to code without explaining the algorithm. Waste of time.
sliding window bro
I don't know why you feel frustrated, you explain it super clear, thanks
the inner while loop can be replaced with If condition.
how tf do you solve these during a coding challenge? I feel like most people just memorize these solutions smh
10 years will get you ready.
Hi Nick, 9:55 why not pause the recording so you have time to think or come up with examples? Or are you setting out to do the recording in one single shot?
I have doubt in while loop, why u added +1 >k?
What's the brute force approach to this?
if the frequency of the maximam count charecter decreases in the while loop the max_count should also decrease
the + 1 is because we are using indexes and we need + 1 for actual length , i.e max length
For an input instance such as :- "AABC" and k = 2, what's the correct answer ? Will it be 3 or 4? Can we replace different characters at a time ? like can we replace both B and C as A or only A/ only B/ only C can be replaced ?
not sure if it works on ABCCDFC and k=1. answer is correct which is 3 but it does allow DFC in the sliding window
I think that while loop is unnecessary, you can just use if(){}, instead of while(){}.
Have you any ancestorial relationship with Walter White.
As a beginner it look like..This guy is sick 😶
This doesn't pass in Leetcode
Anyway I understand it after watching it twice. Would have been better with an extra example lol. Appreciate your work.
Loved your lazy side on 10:04 :D
why don't we have to update max_count in the while loop?
not sure about soo many thumbs down .. u explained it very well !! cheers
just to add algo is good too
You explained very well, man!
Why are we using max_count variable?
Audio balance in earphones is messed up
Good video man! Done is better than perfect hahaha, i prefer this video although obviusly with more examples could be a more clear explanation!
is the space complexity O(1) since the integer array is size of 26?
yes
Code not working
Can someone explain why you don't have to adjust the max_count in the second while loop? Suppose that my maxCount is counting A and I remove A from the left index, why do I not need to decrement my maxCount?
Because it's the *max* and in the 2nd loop you're only decrementing. By definition it cannot go up.
I had the same thought. But it is not required because if you look closely, size of the window never decreases. You can replace while with if and it will still work.
We don't need to recalculate max_count because our goal is to find the substring where the max_count is maximum. The more the repeating characters in our string, the better ('aaaaab' is better than 'aab' because in the first one we have more repeating chars, therefore it's longer) . In the solution, when we move the start pointer forward and don't update the max_count, the substring gets counted as a valid substring (even if it isn't) but it doesn't matter to us because the length of this substring is smaller than the maxLength we found earlier. Try iterating through the second example test case step by step and you'll see for yourself as to why updating the max_count doesn't matter. Hope this helps!
Best Explanation Nick Thanks a lot :)
best explanation
we love you too, nick!
I think you explained it well. thanks, man!
Thanks man, pretty good explanation.
u r really a nice guy
wow explanation....
What's
window_end - window_start - max_count + 1 > k. Can anyone explain that?
It's the number of characters in the window that need to flipped. Number of characters different from the majority character in the window.
Array 0 index based
great explanation.
A bit confusing explanation!
yo i got it
Thank you very much
This guy is great
Cool dude. Good explanation.
You are funny! Good video.
So condescending
" You know what I mean " that is your explanation bruuuh come on you can do better than that.
quick note, solution also works if you use an if statement instead of a while loop