Sliding Window
==================================

Sliding window technique is used to solve subarray or substring problem. Rolling hash is basically a sliding window algorithm.





The window size could be fixed or variable.

Fixed Window
------------------------------

When it is fixed, after finding the window, we just need to move the head and tail index at the same time. The tricky part is from calculating statistics in the sliding window, eg, maximum, minimum, median.

Normally a special data structure is needed to solve fixed sliding window statistics problem.


Sliding Window Maximum
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

 

Example:

.. code-block:: none

  Input: nums = [1,3,2,5,8,7], k = 3
  Output: [3,5,8,8]

.. image:: sw_max.png
  :align: center
  :name: sliding_window_max
  :width: 180



A **monotonic decreasing queue** can be used to solve this problem efficiently.

.. code-block:: c++
  :linenos:

  class monotonic_queue {
  private:
      deque<int> data;
  public:
      void push(int n) {
          while (!data.empty() && data.back() < n)
              data.pop_back();
          data.push_back(n);
      }
      int max() { return data.front(); }
      void pop(int n) {
          if (!data.empty() && data.front() == n)
              data.pop_front();
      }
  };


.. figure:: sw_max_1.png
  :align: center
  :name: sliding_window_max
  :width: 300
  
  In a monotonic decreasing queue, a new item will evicts all the items less than itself. To insert 5 to [4,3,2], all the items are evicted and 5 is the only item after insertion.

.. figure:: sw_max_2.png
  :align: center
  :name: sliding_window_max
  :width: 300

  Insertion of 4 to [5,3,2] will evict 3 and 2, so the resulting queue becomes [5,4].

----


.. code-block:: c++
  :linenos:

  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      monotonic_queue window;
      vector<int> res;
      for (int i = 0; i < nums.size(); i++) {
          if (i < k - 1) { // fill the first k-1 of the window first
              window.push(nums[i]);
          } else { // window slide forward
              window.push(nums[i]);
              res.push_back(window.max());
              window.pop(nums[i - k + 1]);
          }
      }
      return res;
  }

**deque** is needed because we need pop from front and back of the sequential data strucutre.



Sliding Window Meidan
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A **multiset** can be used to solve this problem efficiently. Refer to :numref:`map_set`  for multiset.

.. code-block:: none

  Window position                Median
  ---------------                -----
  [1  3  -1] -3  5  3  6  7        1
  1  [3  -1  -3] 5  3  6  7       -1
  1   3 [-1  -3  5] 3  6  7       -1
  1   3  -1 [-3  5  3] 6  7        3
  1   3  -1  -3 [5  3  6] 7        5
  1   3  -1  -3  5 [3  6  7]       6

.. literalinclude:: code/sw_median.h
  :language: c++
  :emphasize-lines: 2-3,6,9,12
  :linenos:
  :lines: 12-25

Line 12 is to delete one number by value in a multimap.


Variable Window
-----------------------------

The execution of a variable window size problem is a bit more tricky and will require more variables to keep track of where our window begins and ends.


.. figure:: sw.png
  :align: center
  :name: sliding_window

  Sliding Window Technique

Sliding window characteristics:

  #. Sliding window has a start(head) and end(tail)
  #. Sliding window has status that indicate the status of the window
  #. Sliding window grows/shrink toward one direction

Sliding window application principles:

  Sliding window skipped some combinations to improve efficiency, to use sliding window needs to prove these combinations can be skipped.


In terms of implementation, here is the key ideas:

  #. Use nested loop to move window: outer loop to expand the window, inner loop to shrink the window
  #. The outer loop stop condition is the right boundary meets array end
  #. The inner loop stop condition is the status of the window meets requirement, as long as it still meets requirement, shrink the window as possible.


The abstract idea of sliding window algorithm is:

.. code-block:: c++

  int left = 0, right = 0;

  while (right < s.size()) {
      window.add(s[right]);
      while (valid) {
          window.remove(s[left]);
          left++;
      }
      right++;
  }

The data type of the window can vary depending on the situation, such as using the hash table as the counter, or you can use an array to do the same, since we only deal with English letters.

The slightly tricky part is the valid condition, and we might have to write a lot of code to get this updated in real time.


Find All Anagrams in a String
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Given two strings s and p, return an array of all the substrings of s which are p's anagram. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

This is a *fixed-length sliding window* problem, so we need to move the head and tail of the window at the same time.

.. literalinclude:: code/sw_anagram_match.h
  :language: c++
  :linenos:
  :lines: 14-51


Minimum Window Substring
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

For example, S = “ADOBECODEBANC”, T = “ABC”
Minimum substring is “BANC”.

Note: If there is no such substring in S that covers all characters in T, return the empty string "".
If there are multiple such substrings, you can return any one of them.

Brute force way is to find all the substrings and find the shortest one which meets the requirement. The time complexity will be O(N^3).

To get O(N) time complexity, we can use sliding window. The first challenge for this problem is how to determine if the substring is valid. The second is how to move the pointers to find the next valid substring.

With a special mapping data structure, the problem becomes more clear.

.. literalinclude:: code/sw_min_window_substr.h
  :language: c++
  :linenos:
  :lines: 5-27

The sliding window algorithm is basically a two-pointer algorithm. First we find the beginning position of a valid substring, then we expand the ending position.

.. literalinclude:: code/sw_min_window_substr.h
  :language: c++
  :linenos:
  :lines: 29-46

Test cases:

.. literalinclude:: code/sw_min_window_substr_test.cpp
  :language: c++
  :linenos:
  :lines: 9, 13



Longest Substring with At Most Two Distinct Characters
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. literalinclude:: code/sw_max_window_distinct_chars.h
  :language: c++
  :linenos:
  :lines: 12-46


Longest Substring Without Repeating Characters
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


.. literalinclude:: code/sw_max_window_unique_chars.h
  :language: c++
  :linenos:
  :lines: 12-45

.. only:: html

  - https://leetcode.com/problems/longest-repeating-character-replacement/
  - https://leetcode.com/problems/minimum-size-subarray-sum/

Dynamic minimum subarray query could be efficiently solved by segment tree. It will be covered later at :numref:`subarray_minimum_query`.