Understanding the Sliding Window Pattern: Efficient Utilization Through Examples

Introduction

In the world of algorithms and data structures, there are many efficient methods that allow solving various problems with minimal computational resources. One such powerful tool is the Sliding Window Pattern, or the "sliding window" technique. This method allows you to confidently control the processing of data in sequences using a fixed-length dynamic window approach. The main idea of a sliding window is that instead of directly iterating or processing all data elements, we narrow the focus to a certain subset of elements that can be changed and updated as we move along the sequence. This technique finds application in various problems, from finding the maximum substring to time series analysis.

In this article, we will introduce you to the concept of the Sliding Window Pattern by providing a brief description of the theory behind it. We will look at how this method works in the context of data processing, illustrating its application with practical examples. In addition, we will share useful tips on choosing the right situations for using a sliding window and optimizing your code.

So, the first thing you want to do is identify a problem that utilizes the sliding window paradigm.

How do you identify such a problem?

• The problem will be related to a data structure that is ordered and repeatable, such as an array or a string.
• You are looking for a certain subrange within this array/string, for example, the longest, shortest, or a target value.
• There exists an obvious naive or brute-force solution that works in O(N²), O(2^N), or some other large time complexity.

Example 1 - How to Find the Longest Substring without Repeating Characters

Task Description:

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

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols, and spaces.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

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

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Brute force approach

The idea is simple, we fix one letter and iterate over the rest of the string until we encounter a duplicate. We save all the letters in the set, and as soon as we find a duplicate letter, we shift the left border by 1 and start over.

This is a simple but inefficient approach.

Complexity:

1. Time complexity: O(n*n)
2. Space complexity:  O(n)

public int lengthOfLongestSubstring(String s) {
    int max = 0;
    for (int left=0; left<s.length(); stleftart++) {
        Set<Character> set = new HashSet<>();
        for (int right=left; right<s.length(); right++) {
            if (left != right && set.contains(s.charAt(right))) {
                break;
            }
            set.add(s.charAt(right));
         }
         max = Math.max(max, set.size());
    }
    return max;
}

Sliding window approach

The idea of optimization is that we don't want to do only 1 step as soon as we meet a duplicate and start all over again. We will move the left border as long as there is a duplicate.

Complexity:

1. Time complexity: O(n)

2. Space complexity:  O(n)

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int max = 0;
    for (int i=0; i<s.length(); i++) {
         char c = s.charAt(i);
        if (set.contains(c)) {
            while (c != s.charAt(i - set.size())) {
                set.remove(s.charAt(i - set.size()));
            }
        } else {
            set.add(c);
        }
        if (set.size() > max) max = set.size();
    }
    return max;
}

I want to note that I do not store the left border in a separate variable (although it is possible).

Since the left border is only needed when we encounter a duplicate, so I know exactly how many unique characters there were: set.size().

Therefore, I can find the left border by the formula: i - set.size().

The algorithm listed above gives us the following result.

Example 2 - Longest Repeating Character Replacement

Task Description:

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Constraints:

• 1 <= s.length <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achive this answer too.

Solution

This is a standard problem for applying the sliding window technique, we must keep the "window" within certain constraints, in this case the constraint will be the presence of k characters different from the most common.

The idea is to move end and check that the area between start and end can be represented by a single character and we will make less than k replacements. If more than k replacements need to be made between start and end, then we will move start until the rule is satisfied again.

public int characterReplacement(String s, int k) {

    // Frequency map to store character frequencies within window
    Map<Character, Integer> charFreqMap = new HashMap<>();

    int start = 0; // Sliding window start
    int maxFreq = 0; // Store frequency of most frequent character within window
    int maxLength = 0; // Store maximum length of substring with same letters

    for (int end = 0; end < s.length(); end++) {
        char endChar = s.charAt(end);
        charFreqMap.put(endChar, charFreqMap.getOrDefault(endChar, 0) + 1);

        // Update maxFreq with current character's frequency
        maxFreq = Math.max(maxFreq, charFreqMap.get(endChar));

        // Calculate the number of characters that need to be replaced
        int replacementsNeeded = (end - start + 1) - maxFreq;

        // Check if replacements needed exceed k
        while (replacementsNeeded > k) {
            char leftChar = s.charAt(start);
            charFreqMap.put(leftChar, charFreqMap.get(leftChar) - 1);
            start++; // Move start to shrink window
        }

        // Update maxLen with current window size
        maxLength = Math.max(maxLength, end - start + 1);
    }
    return maxLength;
}

I hope this article helped you understand how to solve this type of problem. I will be glad for your feedback.

See you soon! ✌