LeetCode Longest Repeating Character Replacement Solution Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[taiyuguo]

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.

[jdxxmxnd]

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

[apdr]

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!

[janmejaysingh]

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.

[manojboganadham]

what about updating the max_count when we increment the window_start ?

[rajankhatri]

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;

}

[benevolent]

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.

[ishwarshelke]

doesnt matter how much questions u do at the end the way of ur explanation conveys the interviewer how much intelligent u r

[LT-whbl]

Test case: 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.

[hippityhoppity]

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.

[ronakkenia]

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.

[subhedarsanchay]

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?

[jackedelic]

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?

[sahastava]

Great video! Just one suggestion, you can replace the 'while' with 'if', it'll still work

[rohanshah]

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:
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

[Madeinchinaagain]

What mic/audio capture settings do you use? It sounds like I'm wearing headphones when you speak

[rohandevaki]

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?

[saketsuman]

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<k otherwise the LRCR for i will be 1.

Please let me know whats wrong in my thought process and whether it can be solved using dp?

Thanks alot

[МаксимЕремин-ят]

Very nice. We just don't need that while, we can replace it with simple IF statement because we are adding only 1 character so if the substring with that character becomes invalid then we remove only one character from the beginning and add one char to the end. No need to keep this doing in a loop.

[yongconglei]

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?