When should you reach for the sliding window technique, and what makes a problem a good fit?
You use it when the answer is about a run of neighbouring values, and when you can add something on the right and remove something on the left without much work.
So what makes a problem a good fit? Four things.
The first one is that the thing you are looking for is a contiguous run of items. If the answer can skip items, like a subset or a subsequence, then the window does not help.
The second one is that the condition is something you can check in constant time. If you had to walk the whole window every time to see whether it was valid, then moving the window would not save you any work.
The third one is that you can add and remove in constant time. A sliding window over a list works well, and a sliding window over a tree does not, because you cannot take things out of a tree cheaply.
The fourth one is that the answer grows as the window grows in a way that you can exploit, such as the sum of the values in the window, or the number of different letters in it.
a good fit not a good fit
---------------------------------- -----------------------------
longest run with no repeats the longest run with jumps
smallest window with every letter the best set of items
a fixed size window anything that needs sorting
So the rule to remember is this. If the answer is a run of neighbouring items and you can check the run cheaply, then a sliding window is the answer.
The last question in this topic shows it on the simplest possible problem.