Sliding Window Algorithm Code Template

The previous article Summary of Two-Pointer Techniques explained simpler two-pointer techniques for arrays. This article will discuss a slightly more complex technique: the sliding window technique.

The sliding window can be categorized as a fast-slow two-pointer technique, with one fast and one slow pointer moving forward together, forming the window between them. Sliding window algorithms are mainly used to solve subarray problems, such as finding the longest/shortest subarray that meets certain conditions.

This article will provide a framework that ensures you can write correct solutions with ease. Each problem is accompanied by an algorithm visualization panel to help you intuitively understand the sliding window process.

Overview of the Sliding Window Framework

If you use a brute-force solution, you need to nest for-loops to enumerate all subarrays, resulting in a time complexity of $O(N^2)$:

for (int i = 0; i < nums.length; i++) {
    for (int j = i; j < nums.length; j++) {
        // nums[i, j] is a subarray
    }
}

The idea behind the sliding window algorithm technique is not difficult. It involves maintaining a window that slides continuously, and then updating the answer. The general logic of this algorithm is as follows:

int left = 0, right = 0;

while (right < nums.size()) {
    // expand the window
    window.addLast(nums[right]);
    right++;
    
    while (window needs shrink) {
        // shrink the window
        window.removeFirst(nums[left]);
        left++;
    }
}

The code written based on the sliding window algorithm framework has a time complexity of $O(N)$, which is more efficient than the brute-force solution using nested for loops.

What troubles many is not the algorithm's concept but the various detailed issues. For example, how to add new elements to the window, how to shrink the window, and at which stage of window movement to update the results. Even if you understand these details, the code can still easily contain bugs, and it can be frustrating not knowing how to find them.

So today, I will write a framework for the sliding window algorithm code. I've even included where to output debug information. When you encounter related problems in the future, just memorize the framework below and modify three places to ensure no bugs will arise.

Since most examples in this article are problems related to substrings, where a string essentially acts as an array, I'll set the input as a string. When solving problems, adapt according to the specific requirements of the problem:

// Pseudocode framework of sliding window algorithm
void slidingWindow(String s) {
    // Use an appropriate data structure to record the data in
    // the window, which can vary according to the specific
    // For example, if I want to record the
    // frequency of elements in the window, I would
    // If I want to record the sum of elements in the window, I could just use an int
    Object window = ...
    
    int left = 0, right = 0;
    while (right < s.length()) {
        // c is the character that will be added to the window
        char c = s[right];
        window.add(c)
        // Expand the window
        right++;
        // Perform a series of updates to the data within the window
        ...

        // *** Position of debug output ***
        // Note that in the final solution code, do not use print
        // Because IO operations are time-consuming and may cause timeouts
        printf("window: [%d, %d)\n", left, right);
        // ***********************

        // Determine whether the left side of the window needs to shrink
        while (left < right && window needs shrink) {
            // d is the character that will be removed from the window
            char d = s[left];
            window.remove(d)
            // Shrink the window
            left++;
            // Perform a series of updates to the data within the window
            ...
        }
    }
}

// Pseudocode framework of sliding window algorithm
void slidingWindow(string s) {
    // Use an appropriate data structure to record the
    // data in the window, varying with the specific
    // For instance, if I want to record the
    // frequency of elements in the window, I would
    // If I want to record the sum of elements in the window, I can simply use an int
    auto window = ...

    int left = 0, right = 0;
    while (right < s.size()) {
        // c is the character that will be entering the window
        char c = s[right];
        window.add(c);
        // Expand the window
        right++;

        // Perform a series of updates to the data within the window
        ...

        // *** position of debug output ***
        printf("window: [%d, %d)\n", left, right);
        // Note that printing should be avoided in the final solution code
        // Because IO operations are time-consuming and may cause timeouts

        // Determine whether the left side of the window needs to shrink
        while (window needs shrink) {
            // d is the character that will be removed from the window
            char d = s[left];
            window.remove(d);
            // Shrink the window
            left++;

            // Perform a series of updates to the data within the window
            ...
        }
    }
}

# Pseudocode framework for sliding window algorithm
def slidingWindow(s: str):
    # Use an appropriate data structure to record the data
    # in the window, which can vary depending on the
    # For example, if I want to record the
    # frequency of elements in the window, I would
    # If I want to record the sum of elements in the window, I could just use an int
    window = ...

    left, right = 0, 0
    while right < len(s):
        # c is the character that will be added to the window
        c = s[right]
        window.add(c)
        # Expand the window
        right += 1
        # Perform a series of updates on the data within the window
        ...

        # *** position for debug output ***
        # Note that you should not print in the final solution code
        # because IO operations are time-consuming and may cause timeouts
        # print(f"window: [{left}, {right})")
        # ***********************

        # Determine whether the left side of the window needs to be contracted
        while left < right and window needs shrink:
            # d is the character that will be removed from the window
            d = s[left]
            window.remove(d)
            # Shrink the window
            left += 1
            # Perform a series of updates on the data within the window
            ...

// Pseudocode framework for sliding window algorithm
func slidingWindow(s string) {
    // Use an appropriate data structure to record the data in
    // the window, which can vary according to the specific
    // For example, if I want to record the frequency of elements in the window, I use a map
    // If I want to record the sum of elements in the window, I can just use an int
    var window = ...

    left, right := 0, 0
    for right < len(s) {
        // c is the character to be moved into the window
        c := rune(s[right])
        window[c]++
        // Expand the window
        right++
        // Perform a series of updates to the data within the window
        ...

        // *** debug output location ***
        // Note that in the final solution code, do not print
        // Because IO operations are time-consuming and may cause timeouts
        fmt.Println("window: [",left,", ",right,")")
        // ***********************

        // Determine whether the left window needs to shrink
        for left < right && window needs shrink {
            // d is the character to be moved out of the window
            d := rune(s[left])
            window[d]--
            // Shrink the window
            left++
            // Perform a series of updates to the data within the window
            ...
        }
    }
}

// Pseudocode framework for sliding window algorithm
var slidingWindow = function(s) {
    // Use an appropriate data structure to record the data
    // in the window, which can vary according to the
    // For example, if I want to record the frequency of elements in the window, I use a map
    // If I want to record the sum of the elements in the window, I can just use an int
    var window = ...;

    var left = 0, right = 0;
    while (right < s.length) {
        // c is the character that will be moved into the window
        var c = s[right];
        window.add(c);
        // Expand the window
        right++;
        // Perform a series of updates on the data within the window
        ...

        // *** debug output position ***
        // Note that in the final solution code, do not print
        // Because IO operations are time-consuming and may cause timeouts
        console.log("window: [%d, %d)\n", left, right);
        // *********************

        // Determine whether the left side of the window needs to shrink
        while (window needs shrink) {
            // d is the character that will be moved out of the window
            var d = s[left];
            window.remove(d);
            // Shrink the window
            left++;
            // Perform a series of updates on the data within the window
            ...
        }
    }
};

The two places marked with ... in the framework indicate where the window data is updated. In specific problems, your task is to fill in the code logic here. Moreover, these two operations are for expanding and shrinking the window, respectively. You will find that they are completely symmetrical in operation.

On a side note, some readers have commented on my framework, saying that hash tables are slow and it's better to use arrays instead. Others prefer to write very concise code, claiming that my code is excessive and not fast enough. My opinion is that the focus of algorithms is on time complexity, and you just need to ensure that your time complexity is optimal. As for the runtime speed on LeetCode, it's somewhat mystical; as long as it's not outrageously slow, there's no need to optimize at the compilation level. Don't get caught up in unnecessary details.

Besides, my algorithm tutorials focus on the algorithmic ideas. Master the framework thinking first, then feel free to modify the code as you wish. I assure you that no matter how you write it, you'll get it right.

Back to the main topic, let's directly apply this framework to four original LeetCode problems. The first problem will be explained in detail, and the following four can be solved with your eyes closed.

I. Minimum Window Substring

Let's start with LeetCode Problem 76: "Minimum Window Substring", difficulty level: Hard.

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

The task is to find a substring in S (source) that contains all the letters of T (target), and this substring must be the shortest among all possible substrings.

If we use a brute-force solution, the code would look something like this:

for (int i = 0; i < s.length(); i++)
    for (int j = i + 1; j < s.length(); j++)
        if s[i:j] contains all letters of t:
            update the answer

The idea is straightforward, but obviously, the complexity of this algorithm is definitely greater than O(N^2), which is not good.

The sliding window algorithm works like this:

1. We use two pointers, left and right, in the string S, initializing left = right = 0. We call the index interval [left, right) a "window."

2. We continuously increase the right pointer to expand the window [left, right) until the substring in the window meets the requirement (contains all characters in T).

3. At this point, we stop increasing right and start increasing the left pointer to shrink the window [left, right) until the substring no longer meets the requirement (does not contain all characters in T). Each time we increase left, we update the result.

4. Repeat steps 2 and 3 until right reaches the end of the string S.

This approach is not difficult. Step 2 is like finding a "feasible solution," and step 3 is optimizing this "feasible solution" to find the optimal solution, which is the shortest covering substring. The left and right pointers take turns moving forward, and the window size increases and decreases, resembling a caterpillar stretching and shrinking as it slides to the right. This is where the name "sliding window" comes from.

Let's visualize the process. needs and window act as counters, recording the frequency of characters in T and the corresponding characters in the "window," respectively.

Initial state:

Increase right until the window [left, right) contains all characters from T:

Now, start increasing left to shrink the window [left, right):

Continue until the string in the window no longer meets the requirements, and left stops moving:

Repeat the above process: move right first, then left... until the right pointer reaches the end of string S, at which point the algorithm ends.

If you understand this process, congratulations! You've fully grasped the sliding window algorithm concept. Now let's see how to use this sliding window code framework:

First, initialize two hash tables, window and need, to record the characters in the window and the characters needed to complete the set:

// Record the frequency of characters in the window
HashMap<Character, Integer> window = new HashMap<>();
// Record the frequency of characters needed
HashMap<Character, Integer> need = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
    char c = t.charAt(i);
    need.put(c, need.getOrDefault(c, 0) + 1);
}

Next, initialize the two ends of the window using the left and right variables. Don't forget, the interval [left, right) is left-closed and right-open, so initially, the window does not contain any elements:

int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
    // c is the character to be added into the window
    char c = s.charAt(right);
    // move the window to the right
    right++;
    // perform a series of updates to the data within the window
    ...
}

The valid variable represents the number of characters in the window that meet the need conditions. If valid is equal to need.size, it means the window satisfies the conditions and completely covers the string T.

Now, let's apply the template. You only need to think about the following questions:

1. When should we move right to expand the window? What data should be updated when a character is added to the window?

2. When should the window stop expanding and start moving left to shrink? What data should be updated when a character is removed from the window?

3. When should we update our final result: during window expansion or contraction?

If a character enters the window, the window counter should be increased; if a character is about to leave the window, the window counter should be decreased; when valid meets need, the window should be contracted; and the final result should be updated during window contraction.

Here is the complete code:

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;

        int valid = 0;
        // record the start index and length of the minimum coverage substring
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c is the character that will be added to the window
            char c = s.charAt(right);
            // expand the window
            right++;
            // perform a series of updates to the data inside the window
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c)))
                    valid++;
            }

            // determine whether the left side of the window needs to be contracted
            while (valid == need.size()) {

                // update the minimum coverage substring here
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d is the character that will be removed from the window
                char d = s.charAt(left);
                // shrink the window
                left++;
                // perform a series of updates to the data inside the window
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d)))
                        valid--;
                    window.put(d, window.get(d) - 1);
                }                    
            }

        }
        // return the minimum coverage substring
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) {
            need[c]++;
        }

        int left = 0, right = 0;
        // record the number of characters in window that meet the need condition
        int valid = 0;
        // record the start index and length of the minimum covering substring
        int start = 0, len = INT_MAX;
        while (right < s.size()) {
            // c is the character to be moved into the window
            char c = s[right];
            // expand the window
            right++;
            // perform a series of updates to the data within the window
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c])
                    valid++;
            }

            // determine whether the left window needs to be shrinked
            while (valid == need.size()) {

                // update the minimum covering substring here
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d is the character to be moved out of the window
                char d = s[left];
                // shrink the window
                left++;
                // perform a series of updates to the data within the window
                if (need.count(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
                }
            }

        }
        // return the minimum covering substring
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need, window = {}, {}
        for c in t:
            need[c] = need.get(c, 0) + 1

        left = 0
        right = 0
        valid = 0
        # record the start index and length of the minimum covering substring
        start = 0
        length = float('inf')
        while right < len(s):
            # c is the character that will be added to the window
            c = s[right]
            # expand the window
            right += 1
            # perform a series of updates to the data within the window
            if c in need:
                window[c] = window.get(c, 0) + 1
                if window[c] == need[c]:
                    valid += 1

            # determine whether the left side of the window needs to be contracted
            while valid == len(need): 

                # update the minimum covering substring here
                if right - left < length:
                    start = left
                    length = right - left
                # d is the character that will be removed from the window
                d = s[left]
                # shrink the window
                left += 1
                # perform a series of updates to the data within the window
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1


        # return the minimum covering substring
        return "" if length == float('inf') else s[start: start + length]

func minWindow(s string, t string) string {
    need, window := make(map[byte]int), make(map[byte]int)
    for i := range t {
        need[t[i]]++
    }

    left, right := 0, 0
    valid := 0
    // record the start index and length of the minimum covering substring
    start, length := 0, math.MaxInt32
    for right < len(s) {
        // c is the character that will be added to the window
        c := s[right]
        // expand the window
        right++
        // perform a series of updates to the data inside the window
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }

        // determine whether the left side of the window needs to be contracted
        for valid == len(need) {

            // update the minimum covering substring here
            if right - left < length {
                start = left
                length = right - left
            }
            // d is the character that will be removed from the window
            d := s[left]
            // shrink the window
            left++
            // perform a series of updates to the data inside the window
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }

    }
    // return the minimum covering substring
    if length == math.MaxInt32 {
        return ""
    }
    return s[start : start+length]
}

var minWindow = function(s, t) {
    let need = {}, window = {};
    for (let c of t) {
        need[c] = (need[c] || 0) + 1;
    }

    let left = 0, right = 0;
    let valid = 0;
    // record the start index and length of the minimum covering substring
    let start = 0, len = Infinity;
    while (right < s.length) {
        // c is the character to be moved into the window
        let c = s[right];
        // expand the window
        right++;
        // perform a series of updates to the data inside the window
        if (need[c]) {
            window[c] = (window[c] || 0) + 1;
            if (window[c] === need[c]) {
                valid++;
            }
        }

        // determine whether the left side of the window needs to shrink
        while (valid === Object.keys(need).length) {

            // update the minimum covering substring here
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d is the character to be moved out of the window
            let d = s[left];
            // shrink the window
            left++;
            // perform a series of updates to the data inside the window
            if (need[d]) {
                if (window[d] === need[d]) {
                    valid--;
                }
                window[d]--;
            }

        }
    }
    // return the minimum covering substring
    return len === Infinity ? "" : s.substring(start, start + len);
};

In the above code, when we find that the count of a character in the window meets the need, we should update valid, indicating that a character requirement has been satisfied. You will also notice that the two operations to update the data within the window are completely symmetrical.

When valid == need.size(), it means all characters in T have been covered, and we have a feasible covering substring. Now, the window should be contracted to find the "minimum covering substring."

When moving left to shrink the window, the characters within the window are part of a feasible solution. Therefore, updating the minimum covering substring should occur during this contraction phase to find the shortest final result among feasible solutions.

By now, you should fully understand this framework. The sliding window algorithm is not difficult, but the details can be quite bothersome. In the future, when faced with sliding window algorithms, follow this framework to write your code; it will ensure no bugs and save you trouble.

Let's apply this framework to quickly solve a few problems. You'll be able to discern the approach almost instantly.

II. String Permutation

This corresponds to LeetCode Problem 567 "Permutation in String", Medium difficulty:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Note that the input s1 may contain duplicate characters, which significantly increases the problem's difficulty.

This type of problem is a classic sliding window algorithm application. It essentially asks: given a string S and a target T, does there exist a substring in S that contains all characters from T with no extra characters?

First, start by copying the previous algorithm framework code. Then clearly address the questions mentioned earlier to derive the solution:

class Solution {
    // determine if there is a permutation of t in s
    public boolean checkInclusion(String t, String s) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // perform a series of updates to the data within the window
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).intValue() == need.get(c).intValue())
                    valid++;
            }

            // determine if the left side of the window needs to shrink
            while (right - left >= t.length()) {
                // determine if a valid substring is found here
                if (valid == need.size())
                    return true;
                char d = s.charAt(left);
                left++;
                // perform a series of updates to the data within the window
                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue())
                        valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // no substring meeting the conditions was found
        return false;
    }
}

class Solution {
public:
    // determine if there is a permutation of t in s
    bool checkInclusion(string t, string s) {
        unordered_map<char, int> need, window;
        for (char c : t) {
            need[c]++;
        }

        int left = 0, right = 0;
        int valid = 0;
        while (right < s.size()) {
            char c = s[right];
            right++;
            // perform a series of updates to the data within the window
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c])
                    valid++;
            }

            // determine if the left side of the window should shrink
            while (right - left >= t.size()) {
                // here, determine if a valid substring is found
                if (valid == need.size())
                    return true;
                char d = s[left];
                left++;
                // perform a series of updates to the data within the window
                if (need.count(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
                }
            }
        }
        // no substring meeting the criteria was found
        return false;
    }
};

class Solution:
    # determine if there is a permutation of t in s
    def checkInclusion(self, t: str, s: str) -> bool:
        need, window = collections.defaultdict(int), collections.defaultdict(int)
        for c in t: 
            need[c] += 1

        left, right, valid = 0, 0, 0 
        while right < len(s):
            c = s[right]
            right += 1
            # perform a series of updates within the window
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1

            # determine if the left window needs to shrink
            while (right - left >= len(t)):
                # here determine if a valid substring is found
                if valid == len(need):
                    return True
                d = s[left]
                left += 1
                # perform a series of updates within the window
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

        # no valid substring found
        return False

// Determine if there is a permutation of t in s
func checkInclusion(t string, s string) bool {
	need := make(map[rune]int)
	window := make(map[rune]int)

    for _, c := range t {
        need[c]++
    }

    left, right := 0, 0
    valid := 0
    for right < len(s) {
        c := rune(s[right])
        right++
        // Perform a series of updates within the window
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }

        // Determine if the left window needs to shrink
        for right - left >= len(t) {
            // Here, determine if a valid substring has been found
            if valid == len(need) {
                return true
            }
            d := rune(s[left])
            left++
            // Perform a series of updates within the window
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

    // No substring meeting the conditions was found
    return false
}

var checkInclusion = function(t, s){
    var need = new Map();
    var window = new Map();
    for (var c of t) {
        need.set(c, (need.get(c) || 0) + 1);
    }

    var left = 0, right = 0;
    var valid = 0;
    while (right < s.length) {
        var c = s[right];
        right++;
        // perform a series of updates within the window
        if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            if (window.get(c) === need.get(c))
                valid++;
        }

        // determine whether the left side of the window needs to shrink
        while (right - left >= t.length) {
            // here determine if a valid substring is found
            if (valid === need.size)
                return true;
            var d = s[left];
            left++;
            // perform a series of updates within the window
            if (need.has(d)) {
                if (window.get(d) === need.get(d))
                    valid--;
                window.set(d, window.get(d) - 1);
            }
        }
    }
    // no substring found that meets the criteria
    return false;
};

The solution code for this problem is basically identical to that of the "Minimum Window Substring," with only a few changes:

1. In this problem, the left pointer is moved to shrink the window when the window size exceeds t.length(), because for permutations, the lengths should obviously be the same.

2. When valid == need.size(), it indicates that the window contains a valid permutation, so you should immediately return true.

As for how to handle the expansion and contraction of the window, it is exactly the same as in the "Minimum Window Substring."

III. Find All Anagrams

This is LeetCode problem 438 "Find All Anagrams in a String" (Medium difficulty):

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

What's this so-called "letter heterogram"? Just permutations with a pretentious name. Given string S and string T, find all starting indices in S where permutations of T occur.

Directly apply the framework we discussed earlier. Clarify the four key questions mentioned, and you'll solve this problem instantly:

class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        // record the result
        List<Integer> res = new ArrayList<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // perform a series of updates to the data within the window
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // determine whether the left side of the window needs to shrink
            while (right - left >= t.length()) {
                // when the window meets the condition, add the starting index to res
                if (valid == need.size())
                    res.add(left);
                char d = s.charAt(left);
                left++;
                // perform a series of updates to the data within the window
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> findAnagrams(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) {
            need[c]++;
        }

        int left = 0, right = 0;
        int valid = 0;
        // record the result
        vector<int> res;
        while (right < s.size()) {
            char c = s[right];
            right++;
            // perform a series of updates to the data within the window
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }
            // determine whether the left window needs to shrink
            while (right - left >= t.size()) {
                // when the window meets the condition, add the starting index to res
                if (valid == need.size())
                    res.push_back(left);
                char d = s[left];
                left++;
                // perform a series of updates to the data within the window
                if (need.count(d)) {
                    if (window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return res;
    }
};

class Solution:
    def findAnagrams(self, s: str, t: str) -> List[int]:
        need = {}
        window = {}
        for c in t:
            need[c] = need.get(c, 0) + 1

        left = 0
        right = 0
        valid = 0
        # record the result
        res = []
        while right < len(s):
            c = s[right]
            right += 1
            # perform a series of updates to the data within the window
            if c in need:
                window[c] = window.get(c, 0) + 1
                if window[c] == need[c]:
                    valid += 1
            # determine whether the left side of the window should shrink
            while right - left >= len(t):
                # when the window meets the condition, add the starting index to res
                if valid == len(need):
                    res.append(left)
                d = s[left]
                left += 1
                # perform a series of updates to the data within the window
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

        return res

func findAnagrams(s string, t string) []int {
    need, window := make(map[rune]int), make(map[rune]int)
    for _, c := range t {
        need[c]++
    }

    left, right := 0, 0
    valid := 0
    // record the result
    var res []int
    for right < len(s) {
        c := rune(s[right])
        right++
        // perform a series of updates within the window
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        // determine whether the left window needs to shrink
        for right - left >= len(t) {
            // when the window meets the condition, add the starting index to res
            if valid == len(need) {
                res = append(res, left)
            }
            d := rune(s[left])
            left++
            // perform a series of updates within the window
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }
    return res
}

var findAnagrams = function(s, t) {
    let need = {};
    let window = {};
    for (let c of t) {
        need[c] = (need[c] || 0) + 1;
    }

    let left = 0, right = 0;
    let valid = 0;
    // record the result
    let res = [];
    while (right < s.length) {
        let c = s[right];
        right++;
        // perform a series of updates to the data within the window
        if (need[c] !== undefined) {
            window[c] = (window[c] || 0) + 1;
            if (window[c] === need[c]) {
                valid++;
            }
        }
        // determine whether the left side of the window needs to shrink
        while (right - left >= t.length) {
            // when the window meets the condition, add the starting index to res
            if (valid === Object.keys(need).length)
                res.push(left);
                let d = s[left];
                left++;
            // perform a series of updates to the data within the window
            if (need[d] !== undefined) {
                if (window[d] === need[d]) {
                    valid--;
                }
                window[d] = window[d] - 1;
            }
        }
    }
    return res;
};

Similar to finding string permutations, we simply add the starting index to res upon identifying a valid anagram (permutation).

IV. Longest Substring Without Repeating Characters

This is LeetCode Problem 3 "Longest Substring Without Repeating Characters", medium difficulty:

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

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

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.

This problem introduces a slight twist; it doesn't fit a standard template but is simpler to solve with minor framework adjustments:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        // record the result
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // perform a series of updates to the data within the window
            window.put(c, window.getOrDefault(c, 0) + 1);
            // determine whether the left window needs to shrink
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                // perform a series of updates to the data within the window
                window.put(d, window.get(d) - 1);
            }
            // update the answer here
            res = Math.max(res, right - left);
        }
        return res;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;
        int left = 0, right = 0;
        // record the result
        int res = 0;
        while (right < s.size()) {
            char c = s[right];
            right++;
            // perform a series of updates to the data within the window
            window[c]++;
            // determine whether the left window needs to shrink
            while (window[c] > 1) {
                char d = s[left];
                left++;
                // perform a series of updates to the data within the window
                window[d]--;
            }
            // update the answer here
            res = max(res, right - left);
        }
        return res;
    }
};

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = {}
        left, right = 0, 0
        # record the result
        res = 0
        while right < len(s):
            c = s[right]
            right += 1
            # perform a series of updates to the data within the window
            window[c] = window.get(c, 0) + 1
            # determine whether the left window needs to shrink
            while window.get(c) > 1:
                d = s[left]
                left += 1
                # perform a series of updates to the data within the window
                window[d] -= 1
            # update the answer here
            res = max(res, right - left)
        return res

func lengthOfLongestSubstring(s string) int {
    window := make(map[rune]int)
    left := 0
    right := 0
    // record the result
    res := 0

    for right < len(s) {
        c := rune(s[right])
        right++

        // perform a series of updates to the data within the window
        window[c] = window[c] + 1

        // determine whether the left window needs to shrink
        for window[c] > 1 {
            d := rune(s[left])
            left++

            // perform a series of updates to the data within the window
            window[d] = window[d] - 1
        }

        // update the answer here
        if res < (right - left) {
            res = right - left
        }
    }

    return res
}

var lengthOfLongestSubstring = function(s) {
    var window = {};
    var left = 0, right = 0;
    // record the result
    var res = 0;
    while (right < s.length) {
        var c = s.charAt(right);
        right++;
        // update the data within the window
        window[c] = (window[c] || 0) + 1;
        // determine whether the left window needs to shrink
        while (window[c] > 1) {
            var d = s.charAt(left);
            left++;
            // update the data within the window
            window[d] = window[d] - 1;
        }
        // update the answer here
        res = Math.max(res, right - left);
    }
    return res;
};

This simplifies the process, as there is no need for need and valid, and updating the data within the window only requires a simple update to the counter window.

When the value of window[c] is greater than 1, it indicates there are duplicate characters in the window, which is not desirable, and the left should be moved to shrink the window.

The only thing to be mindful of is when to update the result res. We are looking for the longest substring without repeating characters, and at what stage can we ensure the string in the window contains no duplicates?

This is different from before; you should update res after shrinking the window, because the condition for the while loop to shrink is that there are duplicate elements. In other words, once shrinking is complete, the window is guaranteed to have no duplicates.

That's all for the sliding window algorithm template. I hope you understand the concept, remember the algorithm template, and apply it effectively. To recap, when you encounter problems related to subarrays or substrings, if you can answer the following questions, you can apply the sliding window algorithm:

1. When should you expand the window?

2. When should you shrink the window?

3. When should you update the answer?

In Classic Sliding Window Problems, I have listed more classic problems using this thought process to strengthen your understanding and memory of the algorithm, so you'll never fear substring or subarray problems again.