Sliding Window Algorithm

                   Sliding Window Algorithm & Examples 

    Sliding window algorithm is a very useful tool to solve problem about finding an optimal subarray or an optimal substring.  As you can get from the name, this algorithm will keep  two pointer in the input array or string, which may represent a window.  Inside this window is a subarray or substring that satisfy certain properties we want.  Then we keep moving this two pointer like sliding  this window from the beginning to end to find a optimal size window.


   Here are 5 examples that could  illustrate  this algorithm very clearly.

    Example 1: Minimum Size Subarray Sum 

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

     // Java Solution using sliding window approach: 

   Explain:  For this example, window will be the subarray from pointer i to j.  

      while ( j < a.length)    -- > we sliding this window until we reach the end of this array 

  while (sum >= s )      --> as long as the sum from i to j >= s, which means we keep a valid size window  

and we moving our start point i to reduce size of window if possible.

    Example 2 : Longest Substring with At Most Two Distinct Characters 

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “ababcd”,

T is "abab" which its length is 4.

 // Java Solution using sliding window approach: 

  Explain:  Here we have a start pointer and i as end pointer, we use for loop i  try every possible end point and use while loop

                                             while( distinct> 2 ) {

                                         while(--map[s.charAt(start++)]>0); 

                                              distinct --;  

                                        }       

        to adjust start point to keep this window valid.

             maxLen = Math.max(maxLen, i - start+1)

  will record the max Length we had during whole process.

Update:
 Sorry for the confusion code in that wile loop, which did 3 things in one line. Here is the code that is more readable: 

Example 3 : Longest Substring with At Most K Distinct Characters 

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “abacd” and k = 2,

T is "aba" which its length is 3.

Here is a almost identical solution with sliding window approach: 

Explain : We almost have the same code except the condition we move our start point becomes

                  ( distinct > k). 

Update
 Also that one line of code did 3 things together, here is the version that is more readable and I prefer to write in this way 

     Example 4: Max One Problem 

Given a array that contains either 0 or 1 in each position. Also given a number b, which represent how many 0 you can turn into a 1. Need to find the maximum  continuous  1 you could make in this given array. 

  For example : array  A: [ 1,0 ,0 ,1 , 1 , 1 ,0 , 0, 1, 0, 0], number b = 2.   Flip two 0 at index 6 and 7, 

     then array A become [ 1,0, 0, 1,  1 , 1, 1,  1, 1, 0, 0] , which will give us maximum  6 consecutive 1  from index 3 to index  8.  In the end you should return those index of this sequence. So [3,4,5,6,7,8] will be return.     Another example will be A :[ 0 , 1 , 0 , 1, 0 ], b = 1.   array [ 1, 2 , 3] should be return.  

    Suggestion: try it by your self before you look at the solution below.

 Explain: there are explanations on the comment already. Just want to mention that there are lots of different way to solve this question, but sliding window approach is probably the most elegant one to deal with it. 

      Example 5: Minimum Window Substring 

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC". 

Again try it out, before you look at the solution below 

Explain:  

      The whole idea is let every char in T +1 value in the map we created, and as long as we find this same char in S, we  -1 value, and if we successfully covered T.length() many char, which means we find every char in T inside this window.  

       Notice at line 12 I have comment : j++ make conner case work and substring do not need to +1 . So there is two case when we calculate the substring length, 

1:  Start from 0 index until index k, where the length of substring is actually k+1.    

2:  From index i ( i !=0), to index j, i is close( the char at index i is not in range), the length is(  j - i ). 

So for the first situation, we need to add 1 in its length, but since we using j++, which will make this case still work for us. 

      

Update: 

Line 19 is still confusing to me sometime, So here is how we separate 3 things into pieces: 

  

  As you may find out, sliding window is a very elegant tool to solve problems. Hope you enjoy it. 

Enjoy Coding ^^ 

Ye Jiang