Sliding Window Algorithm

The sliding window algorithm is used for finding a pattern with the smallest window size. It is adaptable and moves along until you have found the smallest window size.

It is actually very optimal and done in O(N) time. It has a max scan of 2N operations, and initially it creates a window that fits the pattern. Once found, it amortizes the cost at O(1) for increasing the window size to span the entire list.

So in order to accomplish this, we will need to have two map-type structures. has[] and need[] maps will be used to verify if we have the accurate number of times a character needs to apply to the pattern.

Let's continue with the code:

int has[256] = {0,};
int need[256] = {0,};

int min_window(string text, string pattern) {
   for (int i = 0; i < pattern.size; ++i)
      ++need[pattern[i]];

   int matchedLen = 0;
   int minWindow = text.size() + 1;
   for (int i = 0, j = 0; i < text.size(); ++i) {
      if (need[text[i]] == 0) continue;

      ++has[text[i]];

      if (need[text[i]] >= has[text[i]])
          ++matchedLen;

      if (matchedLen == pattern.size()) {
         while (need[text[j]] == 0 || 
                has[text[j]] > need[text[j]]) {

            if (has[text[j]] > need[text[j]])
                --has[text[j]];

            ++j;
         }
         // Update window size.
         minWindow = std::min(minWindow, i - j + 1);
      }
   }
   return minWindow;
}