Sliding window concept: Never let it slide off your brain

A problem based on sliding window patterns regularly appears in interviews like Facebook, Google, and Amazon. This pattern is simple to understand and apply, however, most of the times candidates do not understand in the first place that the problem is a sliding window problem.

How to identify a sliding window problem?

The first hint is in the problem statement, usually, a sliding window problem asks us to find a subarray or a substring. It means the elements are contiguous, and substring/subarray can be the window we are looking for. So, the idea is to think of a sliding window pattern whenever you hear find a subarray or substring in a given array.
The second hint confirms that the problem is actually to be solved using a sliding window pattern. In the problem, you would be asked to find a substring or subarray with a certain property, for example, find the longest substring with nonrepeating characters.

To summarize, if you are asked to find subarray or substring with a specific property (longest/shortest/whatever), think of sliding window pattern.
Now that we have identified the problem to be a sliding window problem, let’s see how to solve it. There are two kinds of problems, first one has a fixed-length window, for example, find the maximum in a window of K in an array; second are the problems where a window is variable-sized. Problems in the second category are difficult and commonly asked in the interview.

A window has two ends, let’s call them left and right. The window is between these two ends. If the window has a variable size, then the window will expand and shrink.

Always expand the window from the right end and shrink from the left end

When you are solving the problem, initialize left and right as 0, then expand the window by increasing the right. When do we shrink the window or expanding the window? Keep expanding the window until it violates the condition stated in the problem statement. As soon as the violation happens, expansion stops, bookkeeping is done if needed like update the longest variable, etc. We start removing elements from the window from left end until the condition is satisfied again.

Stop when right reaches at the end of the original string. The general pattern of solutions is as follows:

package AlgorithmsAndMe;

public class SlidingWindowProblems {
    
    public int solve(String s){
        
        /* Step 1. Initialize the window of 
           zero size, i.e left and right as 0
         */
        int left = 0;
        int right = 0;
        
        int longest = 0;
        
        //Step 2 : Go on all till right reaches end
        while(right < s.length()) {
            
            /* Step 3: Do some bookkeeping to update 
               the state of the window.
              */

            //Step 4: Expand the window
            right++;

            //Step 5: go on till condition is not valid
            while (left < right /* and Condition is invalid */) {
                
                /*Step 6: Do the book keeping to keep
                track of optimization requirements */
                longest = Math.max(right - left, longest);
                
                /* Step 7: Update the condition. */
                /* Step 8: remove the left most element 
                    from the window.
                 */
                left++;
            }
        }
        
        return longest;
    }
}

With this template code, you have to figure out one thing: how would you maintain the state of the window so that we can quickly check if it is valid or not. It varies from problem to problem. Do not sweat too much about it initially, go with the first thing which can work and then later, optimize it.

Longest substring without repeating character

This problem is available on leetcode as Longest Substring Without Repeating Characters, try it with template provided before going to the solution given below.

Given a string, find the length of the longest substring without repeating characters.

For example, abcabcbb longest string with no repeating characters is abc with length 3.

Hint 1, we are looking for a substring, and hint 2, we are looking for a substring with a specific property (without a repeating character), it means we can use the sliding window approach to solve this problem. In our template, it is important to known when the condition is invalid. To know that a character is repeated, we can use a hashmap, however, a better solution would be a set of character already in the window. Why? Because we do not care about value in the hashmap anyways, all we want to know that a character exists in hashmap, which can be done using set as well without using additional memory for values.

How can we know that condition is invalid? If the new character which comes in the window is already present in the set, then our window violates the no repeating character condition. In that case, we will start removing characters from the left end till a new character can be added to the window. Also, do the bookkeeping to keep track of the longest.

package AlgorithmsAndMe;

import java.util.HashSet;
import java.util.Set;

public class SlidingWindowProblems {

    public int solve(String s){

        /* Step 1. Initialize the window of
           zero size, i.e left and right as 0
         */
        int left = 0;
        int right = 0;

        int longest = 0;

        Set<Character> set = new HashSet<>();
        //Step 2 : Go on all till right reaches end
        while(right < s.length()) {

            /* Window already contains the character
                which we want to add, start shrinking
                the window.
             */
            char c = s.charAt(right);
            if(set.contains(c)){
                //Step 5: go on till condition is not valid
                while (left < right && set.contains(c)) {
                    /*Step 6: Do the book keeping to keep
                    track of optimization requirements */
                    longest = Math.max(right - left, longest);

                    /* Step 7 and 8: updated condition
                        remove the left most element
                        from the window,
                    */
                    set.remove(s.charAt(left));
                    left++;
                }
            }
            
            //Step 3 and 4. Add the right character to the set
            set.add(c);
            right++;
        }

        return Math.max(right-left, longest);
    }
}

In this solution, steps 3 and 4 are at the end because how we do the bookkeeping, if we add the right into the set before checking if already exists, it will fail as a set only stores unique elements.

Longest Substring with At Most 2 Distinct Characters

This problem is asked in Google interview and the problem statement goes like

Given a string, find the longest substring that contains only two unique characters.

For example, given a string abcbbbbcccbdddadacb, the longest substring that contains 2 unique character is bcbbbbcccb.

package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class SubstringWith2DistinctCharacters {

    public int solve(String s){

        /* Step 1. Initialize the window of
           zero size, i.e left and right as 0
         */
        int left = 0;
        int right = 0;

        int longest = 0;

        Map<Character, Integer> map = new HashMap<>();
        int distinct = 0;
        //Step 2 : Go on all till right reaches end
        while(right < s.length()) {

            /* Step 3: Do some bookkeeping to update
               the state of the window.
              */
            char c = s.charAt(right);
            if(!map.containsKey(c)){
                distinct++;
            }
            map.put(c, map.getOrDefault(c, 0) + 1);
            //Step 4: Expand the window
            right++;

            //Step 5: go on till condition is not valid
            while (left < right && distinct > 2) {

                /*Step 6: Do the book keeping to keep
                track of optimization requirements */
                longest = Math.max(right - left, longest);

                /* Step 7: Update the condition. */
                map.put(s.charAt(left), map.get(s.charAt(left))-1);
                
                /* We can decrease distinct count only if the character
                just removed is not any more in window */
                if(map.get(s.charAt(left)) == 0){
                    distinct--;
                }
                /* Step 8: remove the left most element 
                    from the window.
                */
                left++;
            }
        }

        return Math.max(right - left, longest);
    }
}

This problem is a straight forward case of a sliding window and perfectly fits in our template. All we had to do is to figure out how to quickly validate the state of the window using a map. Now, can you solve another similar problem called: Longest Substring with At Most K Distinct Characters or a subarray with K different elements or Max Consecutive Ones III

If you are looking for a quick crash course where you can prepare for 80% of your interview in 2 weeks with these pattern-based learning, please reach out to us at [email protected] or book a free demo session.

Longest Substring Without Repeating Characters

Given a string, find the longest substring without repeating characters in it. For example,

Input:
S = "abcaabaca" 
Output:
3
Explanation:
The longest substring without repeating characters will be "abc"

Input: 
"bbbbb"
Output:
1
Explanation:
The answer is "b", with a length of 1.

A brute force solution will be to scan all substrings of the given string and check which one has the longest length and no repeating characters. For a string with size n, there will be n * (n-1) substrings, and to check it each for unique characters, it will take n comparison in the worst case. So, the worst-case complexity of this algorithm is O(n3) with additional space of O(n). The code is simple enough.

package com.company;

import java.util.HashMap;

/**
 * Created by sangar on 1.1.18.
 */
public class NonRepeatingCharacters {

     boolean allUniqueCharacters(String s, int start, int end) {

        HashMap<Character, Boolean> characters = new HashMap<>();

        for (char c : s.substring(start, end).toCharArray()) {
            if(characters.containsKey(c)) return false;
            characters.put(c, Boolean.TRUE);
        }
        return true;
    }

    int longestSubstringWithoutRepeatingCharacters(String s) {
        int len = s.length();
        int maxLength = 0;
          
        for (int i =0; i < len; i++){
            for (int j=i+1; j<len; j++){
                int length = j-i;
                if (allUniqueCharacters(s, i, j)){
                    maxLength = Integer.max(maxLength, length);
                }
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcdabcbb";
        System.out.println(longestSubstringWithoutRepeatingCharacters(s));
    }
}

Sliding window approach

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in array/string which defined by start and end indices. A sliding window is a window which “slides” its two boundaries in a certain direction.
Read fundamentals and template for a sliding window to understand more about it and how it is applied to problems.

In the brute force approach, we repeatedly checked each substring for unique characters. Do we need to check each substring? If a substring s[i,j-1] contains non repeating characters, while adding jth character, check if that character is already present in substring s[i,j-1]. Since we scan substring to ascertain the uniqueness of new characters, the complexity of this algorithm is O(n2).

How about optimizing the scanning part? What if a hash is used to store characters which are already seen in substring s[i,j-1]. In that case, checking the uniqueness of a new character is done in O(1) and overall algorithm complexity becomes linear.

 public  static int longestSubstringWithoutRepeatingCharacters(String s) {
        int len = s.length();
        HashMap<Character, Boolean> characters = new HashMap<>();

        int maxLength = 0;
        int start = 0;
        int  end = 0;
        while (start < len && end < len) {
            //Check only the last character.
            if(!characters.containsKey(s.charAt(end))){
                characters.put(s.charAt(end), Boolean.TRUE);
                end++;
            }
            else {
                int currentLength = end-start;
                maxLength = Integer.max(maxLength, currentLength);
                //Move start of window one position ahead.
                characters.remove(s.charAt(start));
                start++;
            }
        }
        return maxLength;
    }

If a character already present in substring s[i,j-1], that means, it cannot be added to the longest substring. Find the length of substring (j-i) and compare it with the current maximum length. if it is greater, the max length of the longest substring without repeating characters is (j-i).
At last move the window to the position of duplicate.

Below is an example execution of the above code.
longest substring without repeating characters

Longest substring without repeating characters : 3

There is a small optimization that helps us to skip more characters when repeating character is found instead of skipping one at a time. Store the index of each character seen in substring [i,j-1].  While processing jth character, if it is already in the hash, we know the index k where that character is in the string. There is no way that any substring can contain unique characters till k and j are in it. So, we skip all indices from i to k and start from k+1 instead of i+1 as in the above method.

Show me the optimized code

  public static int longestSubstringWithoutRepeatingCharacters3(String s) {
        int len = s.length();
        HashMap<Character, Integer> characters = new HashMap<>();

        int maxLength = 0;

        for (int start=0, end = 0; end <len; end++) {
            if (characters.containsKey(s.charAt(end))) {
                //find the index of duplicate character.
                int currentIndex = characters.get(s.charAt(end));
                start = Integer.max(currentIndex, start) + 1;
            }
            int currentLength = end - start;
            maxLength = Integer.max(maxLength, currentLength);
            //Update new location of duplicate character
            characters.put(s.charAt(end), end );
        }
        return maxLength;
    }

Complexity of find longest substring without repeating characters is hence O(n) with additional space complexity of O(n).
Please share if something is wrong or missing. We would love to hear from you.