# Sliding Window

See:

<https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92007/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem>.

## Similar Problems:

* [Minimum Window Substring](/lintcode/two_pointers/minimum_window_substring.md): <https://leetcode.com/problems/minimum-window-substring/>
* [Longest Substring Without Repeating Characters](/lintcode/two_pointers/longest_substring_without_repeating_characters.md): <https://leetcode.com/problems/longest-substring-without-repeating-characters/>
* <https://leetcode.com/problems/substring-with-concatenation-of-all-words/>
* [Longest Substring with At Most Two Distinct Characters](/lintcode/two_pointers/longest-substring-with-at-most-two-distinct-characters.md): [https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/](/lintcode/problem-solving-summary/sliding-window.md)
* [Longest Substring with At Most K Distinct Characters](/lintcode/two_pointers/longest_substring_with_at_most_k_distinct_characters.md)
* <https://leetcode.com/problems/find-all-anagrams-in-a-string/>

## Window Sliding Technique

This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.

## Template

```java
public class Solution {
    public List<Integer> slidingWindowTemplateByHarryChaoyangHe(String s, String t) {
        //init a collection or int value to save the result according the question.
        List<Integer> result = new LinkedList<>();
        if(t.length()> s.length()) return result;

        //create a hashmap to save the Characters of the target substring.
        //(K, V) = (Character, Frequence of the Characters)
        Map<Character, Integer> map = new HashMap<>();
        for(char c : t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        //maintain a counter to check whether match the target string.
        int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate.

        //Two Pointers: begin - left pointer of the window; end - right pointer of the window
        int begin = 0, end = 0;

        //the length of the substring which match the target string.
        int len = Integer.MAX_VALUE; 

        //loop at the begining of the source string
        while(end < s.length()){

            char c = s.charAt(end);//get a character

            if( map.containsKey(c) ){
                map.put(c, map.get(c)-1);// plus or minus one
                if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition).
            }
            end++;

            //increase begin pointer to make it invalid/valid again
            while(counter == 0 /* counter condition. different question may have different condition */){

                char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer
                if(map.containsKey(tempc)){
                    map.put(tempc, map.get(tempc) + 1);//plus or minus one
                    if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition).
                }

                /* save / update(min/max) the result if find a target*/
                // result collections or result int value

                begin++;
            }
        }
        return result;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/problem-solving-summary/sliding-window.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.