educative.io

The "if" statement might cause some bugs

Courses
,
#1

if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
char leftChar = str.charAt(windowStart);
letterFrequencyMap.put(leftChar, letterFrequencyMap.get(leftChar) - 1);
windowStart++;
}

the maxRepeatLetterCount could be changed if “windowStart” is pointing the character which has maxRepeatLetterCount . Then, windowStart increase 1, and maxRepeatLetterCount decrease 1, so this part of code need to be processed one more time. So I think using while is correct and each time we need to calculate maxRepeatLetterCount. Is there someone can explain this part? I’m very confused.

2 Likes
#2

yeah, I have the same question.
But maxRepeatLetterCount won’t be changed in while loop even when the start char is removed.
With or without updating maxRepeatLetterCount in while loop you’ll have the same result.
ex. “bbcdef” k = 2

before go to while loop maxRepeatLetterCount is 2 and end = 4, start = 0.
when in the while loop, maxRepeatLetterCount is 2 and end = 4, start = 1
b’s occurrence became 2 to 1 in while loop, but the maxRepeatLetterCount is compare with the occurrences of the currently removed char b max(2, 1) = 2

#3

The solution has no bug. If you are searching for the shortest window you will need a while window. However here we are searching for the longest window. In no circumstances do you need to ever shrink the window, EVEN when the window does not meet the criteria. Just focus on when you can grow the window.
I don’t know how to explain this better, it took me like good half an hour to figure it out and I modified all the slide window codes to ‘if’ in the cases we are looking for the longest window/subarray. this will reduce the complexity from 2N to 1N but really still the same.

4 Likes
#5

This was very helpful!
I think we can maybe see it in this sense: We have already found the current longest string to be of length 4, then by using the if statement we are essentially keeping the window size same but just shifting the window_start 1 by 1 to the right with the window_end variable. We are doing this because now we only need to find any windows with length >4.

1 Like
#6

@Design_Gurus

Jack1 mentioned ‘In no circumstances do you need to ever shrink the window, EVEN when the window does not meet the criteria. Just focus on when you can grow the window.’

It seems we grow the window even when it DOES NOT meet the criteria (repeating letter + k non-repeating letter)
If it does not matter if the criteria is met, why bother removing exactly one char from the window?

With a string like A a D c E b b, using your provided solution, at certain points the window contains ** D c E b** which does not fulfil the criteria (taking k = 2) at all, as there are 4 non-repeating letters

but we still take the length of this?

Can you elaborate on this? Better yet, could you create a diagram solution for this question?

Would love to learn. Thanks!