Sliding Window

Authors: @heiheihang @wingkwong

Overview

Sliding Window is a technique used for iterating through a finite data set, typically an array, in a specific and controlled way. It involves creating a window, which is a subset of the data, that "slides" through the larger data set, typically one element at a time, while performing a specific operation on each subset of the data.

The size of the window and the number of elements it moves at each step can be adjusted to suit the needs of the specific problem being solved. The technique is commonly used in algorithms that involve finding patterns or trends in data, such as finding the maximum/minimum value in a set of data, or counting the number of occurrences of a specific element.

Sliding window can be applied in various problems such as:

• Finding the maximum/minimum value in a set of data.
• Counting the number of occurrences of a specific element.
• Finding the longest substring without repeating characters.
• Finding the maximum sum of a sub-array of size $k$.

Overall, the sliding window technique is a useful approach for solving specific types of problems that involve iterating through a data set in a controlled way, such as in pattern matching, data analysis, and statistics. It allows for an efficient and controlled iteration of a data set, which can lead to improved performance and more accurate results.

Example 1: 1876 - Substrings of Size Three with Distinct Characters

A string is good if there are no repeated characters.

Given a string s, return the number of good substrings of length three in s.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

For example, with this input:

s = "xyzzaz"

The substrings with length of 3 are:

s1 = "xyz" #index 0-2
s2 = "yzz" #index 1-3
s3 = "zza" #index 2-4
s4 = "zaz" #index 3-5

Among these substrings, the only substring with distinct characters is "xyz".

In this problem, we need to keep a window of substrings of length 3.

We can use the following strategy:

• left_pointer to keep track of the left character of the substring length of $3$
• right_pointer to keep track of the right character of the substring length of $3$
• We check if the following characters are unique:
  • s[left_pointer]
  • s[left_pointer + 1]
  • s[right_pointer]

Let's take a look at the following solution:

Python

Written by @heiheihang

def countGoodSubstrings(self, s: str) -> int:
        # two pointers to keep track of sliding window
        left_pointer = 0
        right_pointer = 2
        unique_substring_count = 0
        # when the sliding window is within s
        while (right_pointer < len(s)):
            # we declare the 3 characters in the sliding window
            first_char = s[left_pointer]
            second_char = s[left_pointer + 1]
            third_char = s[right_pointer]
            #  if all characters are unique, add 1
            if (first_char != second_char and first_char != third_char and second_char != third_char):
                unique_substring_count += 1
            # shift the sliding window right
            left_pointer += 1
            right_pointer += 1
        # return result
        return unique_substring_count

C++

Written by @wingkwong

class Solution {
public:
    int countGoodSubstrings(string s) {
        int left_pointer = 0;
        int right_pointer = 2;
        int unique_substring_count = 0;
        while (right_pointer < s.length()) {
            char first_char = s[left_pointer];
            char second_char = s[left_pointer + 1];
            char third_char = s[right_pointer];
            if (first_char != second_char && first_char != third_char && second_char != third_char) {
                unique_substring_count += 1;
            }
            left_pointer += 1;
            right_pointer += 1;
        }
        return unique_substring_count;
    }
};

Java

Written by @wingkwong

class Solution {
    public int countGoodSubstrings(String s) {
        int left_pointer = 0;
        int right_pointer = 2;
        int unique_substring_count = 0;
        
        while (right_pointer < s.length()) {
            char first_char = s.charAt(left_pointer);
            char second_char = s.charAt(left_pointer + 1);
            char third_char = s.charAt(right_pointer);
            
            if (first_char != second_char && first_char != third_char && second_char != third_char) {
                unique_substring_count += 1;
            }
            
            left_pointer += 1;
            right_pointer += 1;
        }
        
        return unique_substring_count;
    }
}

In this problem, the size of the sliding window is constant. There are harder problems with varying sliding window size, but you need to learn Hash Map first.

Suggested Problems

Problem Name	Difficulty	Solution Link
1852 - Distinct Numbers in Each Subarray	Medium	View Solutions
1004 - Max Consecutive Ones III	Medium	View Solutions
1876 - Substrings of Size Three with Distinct Characters	Medium	N/A