Start a Thread

Subscribe You’re not receiving notifications from this thread.

A Birds Eye View Into Sliding Windows (Main Thread)

General • Asked over 1 year ago by Anonymous

Jake from AlgoDaily Commented on Oct 26, 2019:

This is the main discussion thread generated for A Birds Eye View Into Sliding Windows.

Anonymous Commented on Oct 26, 2019:

I think there is an error here? Should it not be

map[s[end]] -= 1


s[end] -= 1


Jake from AlgoDaily Commented on Oct 27, 2019:

Yes! Great call-- updating and improving the lesson.

dipo.elegbede Commented on Nov 20, 2019:

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?

Thank you.

Anonymous Commented on Jul 30, 2020:

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.

Dmitry Pavlov Commented on Jan 03, 2021:

I'm confused a bit :) Please, help

First 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?

Jake from AlgoDaily Commented on Jan 03, 2021:

Hi Dmitry Pavlov,

Thanks for much catching that-- there was a bug on the last line. Instead of slicing the input string from begin to substr_size, it should've been from begin to 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 :-)

Jake from AlgoDaily Commented on Jan 07, 2021:

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!

Dmitry Pavlov Commented on Jan 07, 2021:

Thank you, Jake!