🙏

জয়  শ্রী  রাম

🕉

---

How to identify if a problem can be solved by Sliding Window Approach ?

Below are the characteristics of the problems which could often be very easily solved by Sliding Window approach:

• The problem will involve a data structure that is ordered and iterable like an array or a string.
• You are looking for some subrange in that array/string, like a longest, shortest or target value.
• There is an apparent naive or brute force solution that runs in O(N²), O(2^N) or some other large time complexity.
• The problem requires you to look for some kind of optimal solution, like the longest sequence or shortest sequence of something that satisfies a given condition exactly.

We will learn the Sliding Window technique by solving a common problem called Minimum Window Substring. The problem statement is given below:

• Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".
  Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.
  
  Example 1:
  Input: s = "KEMPLANTERNMPEGOWDA", t = "LAMP"
  Output: "LANTERNMP"
  
  Example 2:
  Input: s = "XYZ", t = "XYZ"
  Output: "XYZ"
  
  Example 3:
  Input: s = "XYZ", t = "abc"
  Output: ""

The naive way to solve this problem would be to start with the substring length equal to the length of t and search for all substrings with that length to see if there is any such substring which contains all the characters in t. Notice that you won't gain anything by starting with a smaller length substring because in order to contain all characters in t the substring should be at least of the length of t. If you see that there exists no such substring then you do the same thing for substring length = ((length of t) + 1), ((length of t) + 2).... all the up to the length of s. You stop the process as soon as you get the first substring that contains all the characters in t.

This is a very inefficient O(N²) algorithm. What’s happening here is that you are missing out a lot of good information on each pass by mandating yourself to look at fixed length windows, and you’re re-examining a lot of parts of the string that don’t need to be re-examined. You’re throwing out a lot of good work, and you’re re-doing a lot of useless work .

This is where the idea of a window comes in. Your window represents the current section of the string/array that you are looking at and usually there is some information stored along with it in the form of constants. At the very least it will have 2 pointers, one indicating the index corresponding beginning of the window, and one indicating the end of the window. You usually want to keep track of the previous best solution you’ve found so far, and at the end return the overall best solution.

Two Major Actions: Expanding and Shrinking/Contracting:

Two very important activities in Sliding Window technique are Expansion and Contraction or Shrinking.

We would go on expanding the window till we get a window that satisfies our condition. Once we have gotten such window we would be looking for if the whole window is at all essential or not. If there is any non-essential part of window we would get rid of that part and shrink the window. An example is: say we are looking for the smallest window possible that satisfies our condition. When expanding we would get a window but it may not be the smallest. In the shrinking phase we see if we can optimize the length of the window and can shrink the same window which still satisfies our condition. For example: if we are looking for all characters in "ABC" in the smallest possible window in "BABAC", while we are in the expansion phase we might grab the window "BABAC" because it satisfies our condition that the window should contain all of the characters in "ABC", but in the shrinking phase we would see that we do not need the entire window "BABAC", because the first "BA" portion is non-essential. We shrink the window from the beginning and get an optimized window "BAC".

As we would see later, in most cases we would be shrinking the first part of the expanded window. It is because generally we stop expanding when the condition is satisfied for the first time. So if we exclude the last element of the window the condition may not hold. So in most cases we would be that the beginning of the window is getting shrunk. In our above example: see how we stopped expanding when we got 'C' in "BABAC". Now if we shrink the window from ending we would lose 'C' and that would result in not satisfying the condition. It would become clearer when we see more examples in the next several chapters.

Java Code:

The below code shows how we can implement an efficient solution for Minimum Window Substring problem using Sliding Window technique. I have put all the implementation logic in the inline comments.




Login to Access Content

Python Code:

Login to Access Content




Time Complexity of Sliding Window technique: O(N) where N is the size of the given input. This is because none of the two pointers go backward at any point of time. Whenever we expand or shrink the pointers move only in the forward direction. So both pointers move O(n) steps.

Space Complexity of Sliding Window Technique: For running Sliding Window technique all we need are two pointers to keep track of the beginning and end of the window. This can be done in constant space. So, space complexity = O(1). depending on the problem you are solving and the data structures you are using your overall space complexity might be worse than this. But, Sliding Window on its own take O(1) space.

PRO Tip:

Often times in a coding interview, if the interviewer gives a hint that he/she is looking for a linear O(N) algorithm, chances are high that the problem could be solved by Sliding Window.

Problem Solving:

Don't forget to check out the below problems to have a lasting hands-on knowledge and deep understanding of Problem Solving using Sliding Window and Two Pointers approach:

• Grumpy Shopkeeper
• Longest Substring With Atmost Two Distinct Characters
• Longest Substring With Atmost K Distinct Characters
• Longest Substring Without Repeating Characters
• Substring With Concatenation of All Words
• Find All Anagrams
• Repeated DNA Sequences

Instructor: