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 , find the length of the without repeating characters. s longest substring Constraints: 0 <= s.length <= 5 * 10^4 consists of English letters, digits, symbols, and spaces. s 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: Time complexity: O(n*n) 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: Time complexity: O(n) 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 and an integer . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most times. s k k Return . the length of the longest substring containing the same letter you can get after performing the above operations Constraints: 1 <= s.length <= 105 consists of only uppercase English letters. s 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 technique, we must keep the "window" within certain constraints, in this case the constraint will be the presence of characters different from the most common. sliding window k The idea is to move and check that the area between and can be represented by a single character and we will make less than replacements. If more than replacements need to be made between and , then we will move until the rule is satisfied again. end start end k k start end start 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! ✌

Understanding the Sliding Window Pattern: Efficient Utilization Through Examples

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

How to Design a Messaging Service in Your 45-Minute System Design Interview

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

How to Design a Messaging Service in Your 45-Minute System Design Interview

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps