General • Asked over 1 year ago by Anonymous
This is the main discussion thread generated for A Birds Eye View Into Sliding Windows.
I think there is an error here? Should it not be
map[s[end]] -= 1
s[end] -= 1
Yes! Great call-- updating and improving the lesson.
I need some clarification with the first while loop:
while end < len(s):
What tells the pointer to move to the next char ?
Let's take 'H' for example: 'H' is not in the substring so we won't go into the if block.
This is also true for the next while loop checking counter.
This takes us straight to the return statement which doesn't look like what we want here as we have only looked at the first letter in the string.
I am thinking there should be a place we increment end outside the if loop else end would always stand at 0 except we are able to get into the if loop but I can't seem to see where we move the pointer to 'G' and then 'F', then 'D', then 'S' before 'A' which is the first time we go into the first if block and get end incremented.
My question therefore is:
How does the code let me move to 'G' since 'H' is not in the substring?
I tried to copy the sample code and run in my machine. If the input like this
print(min_window("zabcde", "ad")), the inner while loop will be an infinity loop. Please check.
I'm confused a bit :) Please, help
print(min_window("abcalgosomedailyr", "ad")) prints "algosom". It doesn't look right :)
And, second, what correct answer to this problem should be in this case: "algosomed" or "da"? I don't get from text. Does order of characters in found substring matter and should it match with order of characters in pattern (req_chars) or not?
Hi Dmitry Pavlov,
Thanks for much catching that-- there was a bug on the last line. Instead of slicing the input string from
substr_size, it should've been from
begin + substr_size, exclusive of the last character.
The correct answer should be
algosomed since we need to retain the order of the input string characters in the found substring. I'll also add a note about order in the updated tutorial!
It seems this is a confusing topic for many, so I'll be producing a video for this. Stay tuned :-)
Hi Dmitry Pavlov,
I made a follow up video explaining how the sliding window method works in detail, by stepping through execution. I also brushed up the written tutorial a bit, hope it's clearer now!
Thank you, Jake!