Sliding Window Algorithm technics.
Solving algorithm questions can be tricky and challenge. Sometimes you may feel like it is an endless tunnel because you just simply don’t know how to approach to come up with the solution(whether the level of difficulty of the algorithm problem is easy or hard). So today I would like to share with you a technique that can be very helpful when solving a question and that is called the window sliding technique.
Let’s talk about what is a window sliding technique is, according to GeeksforGeeks, it’s defined as ‘The window Sliding Technique shows how a nested for loop in some problems can be converted to a single for loop to reduce the time complexity’. In order words, it’s a method that involves linear sequences, such as arrays. A window is a contiguous sequence that is part of an array. As the name suggests, the window is slid over the array. For example, the leetcode question 3-Finding the Longest Substring Without Repeating Characters, it asking to return the longest substring without repeating characters from the given input s.
To solve this problem window sliding technique can be best understood,
Step 1)
a b c b b c a d
^
longest Substring length: 1
=============================Step 2)
a b c b b c a d
^ ^
longest Substring length: 2
=============================Step 3)
a b c b b c a d
^ ^ ^
longest Substring length: 3
=============================Step 4)
a b c b b c a d
^ ^ ^ x (we find the repeating of 'b', and 'b')
longest Substring length: 3
=============================Step 5)
a b c b b c a d
^ (Repeat this step 1-4) until last index)
longest Substring length: 3
=============================
Okay, so what just happened here? Let’s take a look at step 1. Imagine there is a pointer and start from the first index. Step2) we see that the first index and second index are not repeating a letter therefore we keep the window from the beginning to the next index(“ab”). Keep repeat for step 3). Now let’s stop at step 4), we actually do see there is a duplicate letter “b” so that can not be substring so we stop the window sliding continuation and start again from the second index and we repeat this procedure until the last index. Cool right?