How to Use the Sliding Window Approach to Find the Smallest Substring Containing Elements From an Array

amkemp
amkemp
Jun 10, 2020 · 6 min read

Today I’m going to explain how to use the sliding window approach to solve a problem.

Like many others out there I have been doing all of the algorithm problems to prepare for technical interviews. One thing I have found that has helped me improve is learning some of the patterns that can be used to solve these problems. There is a great course on educative.io called Grokking the Coding Interview: Patterns for Coding Questions that has been really helpful in improving my skills. One of the patterns they discuss in the course is the sliding window approach, and today I’m going to talk through how to use it to solve an algorithm problem that asks us to find the smallest substring that contains all characters of an array.

So, What is a sliding window?

The basic idea behind this approach is to make a starting point and an ending point for your window and then make the window bigger by moving the ending point. As long as it is still looking for what you need it to look for keep moving the ending point. When when it is no longer doing its job you make the window smaller again by moving the starting point until it starts doing what you want it to again. Usually during this process you keep track of what you found, that might be the length of a substring, it might be characters in a substring. There are a ton of variations of problems where this technique is useful. Today we are going to look for the smallest substring that has the elements of a given array. Here is our question:

Where do we start?

I like to start any algorithm problem by making sure I understand the question and then writing out what my expected inputs and outputs are as well as any notes I want to remember about those values. For this problem I would write something like this:

Then we figure out an example input. I usually try to do more than one so I can at least have two different results to use to check my work:

Next I would write out what I plan to do in pseudocode, in order to keep this explanation from being really repetitive I will include the steps below the code as I do them. I would talk through these steps before beginning to code my approach, and I would list them out as comments in my code as I thought of them so that when I am ready to go back and start coding my approach I can add my code underneath them and reference the steps in case I forget where I am and what my plan was. This helps with the interview nerves.

Start Coding

Once you are comfortable with your approach you can start coding. My pseudocode/explanation is beneath each code snippet:

  1. Make a variable for the start of my window
  2. Make a variable to hold my result
  3. Make an object to hold the counts of the characters in my array
  4. Make a counter variable to count how many of my unique characters I have come across so far
  1. Loop through my array of unique characters to build an object with each character with a starting value of 0, we don’t need an else case because we know these are all unique. For some reason sometimes when I solve this problem I mess up and try to loop through the string at this point. You want to be looping through the array of unique characters. You can also use a Map to store these values but I’m going to use an object literal because I think it is a little easier to see what you are doing for explanation purposes.
  1. Loop through the string with your iterator representing the end of the window.
  2. See if each character you come to is in your object.
  3. If it is in your object and its value is still zero then increment our unique counter.
  4. Add one to the count of that key in the object.
  5. While our uniqueCounter is equal to our array length, aka we’ve found all of the unique elements in our array, let’s make a variable to hold on to the length of our current window by subtracting our windowEnd minus windowStart and adding one.
  6. If our current window length is equal to our array length then let’s just go ahead and return that substring because it only has one of each of our elements in it, we won’t be finding a shorter string that has them all.
  7. If our current result string is still empty at this point OR if the current window size is less than the current length of our result string then that means we have found a shorter substring, so let’s set our result string to be a substring from our startWindow to our endWindow plus one because the substring method is not inclusive of our end index in JavaScript.
  8. Now let’s shrink our window so we can keep looking to see if we can find a shorter substring. Let’s use a variable to keep track of the character at the start of our window.
  9. Since we are shrinking our window at this point we want to stop thinking about that character that was at the start of the window since we are moving on. If that character at our window start is in our object we will subtract one from that key’s value since we aren’t counting it anymore. Then if subtracting that character would put our count of that key in our object back to zero we will remove one from our uniqueCounter as well since it was one of the unique characters we were counting.
  10. Increase our startWindow variable by one to finish our shrink the window process.
  11. At the end return the result. Always return something!!
  12. Finally, once you have finished your code, walk through the code with your example inputs to find any mistakes you may have made. I forget to do this step all the time but making myself take the time to walk through my code before running it has really improved my problem solving skills. I highly recommend it.

Hopefully this explanation helped someone to better understand how to use the sliding window method, again, it’s basically:

  1. Make a window
  2. Is it still doing what you need it to do? If so move the window end
  3. If it isn’t make the window smaller by moving the window start
  4. As you go keep track of what you need to keep track of for this specific problem
  5. Continue until you are done

Full Code Below

I hope this explanation helps someone else to understand the sliding window pattern. If you have questions or just want to connect, please connect with me on LinkedIn. I am in the middle of my job search so if you have any useful leads for a junior developer please reach out!

The Startup

Get smarter at building your thing. Join The Startup’s +789K followers.

Sign up for Top 10 Stories

By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

amkemp

Written by

amkemp

Ann-Marie Kemp is a full stack software engineer living in New York City. She is currently studying algorithms and job hunting for a junior developer position.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +789K followers.

amkemp

Written by

amkemp

Ann-Marie Kemp is a full stack software engineer living in New York City. She is currently studying algorithms and job hunting for a junior developer position.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +789K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store