# 3. Sliding Window

## Sliding window

### Template

```java
public int slidingWindow(String s) {
    // ========= 模板：定义相关数据结构，初始化工作============
    HashMap<Character, Integer> windowMap = new HashMap<>();
  
    int left, right, res;
    left = right = res = 0;

    // ================== 模板：开始滑动窗口=====================
    while (right < s.length()) {

        // =========== 模板：向右滑动窗口，装填满足的字符到map中==========
        char c = s.charAt(right);
        right++;
        windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

        // =========== 根据题意：此时“有可能”出现满足条件的解 ==========
        // 判断左侧窗口是否要收缩
        while (window_map.get(c) > 1) {
            char d = s.charAt(left);
            left++;
            // 进行窗口内数据的一系列更新
            windowMap.put(d, windowMap.getOrDefault(d, 0) - 1);
        }
        // 在这里更新答案
        res = Math.max(res, right - left);
    }
    return res;
}
```

### Typic problems

* Find longest no repeated substring

<pre class="language-java"><code class="lang-java"><strong>//Find the length of longest no repeat substring from a given string
</strong><strong>public int lengthOfLongestNoRepeatSubstring(String s) {
</strong>    Map&#x3C;Character, Integer> charMap = new HashMap&#x3C;>();
    int left = 0, right = 0, result = 0;
    while (right &#x3C; s.length()) {
        //Expand the window
        char ch = s.charAt(right);
        charMap.put(ch, charMap.getOrDefault(ch, 0) + 1);
        right++;

        //shrink the window
        while (charMap.get(ch) > 1) {
            char leftChar = s.charAt(left);
            charMap.put(leftChar, charMap.getOrDefault(leftChar, 0) - 1);
            left++;
        }

        //Save the results
        result = Math.max(result, right - left);
    }
    return result;
}
</code></pre>

* Minimum coverage window substring

```java
//Find the minimun substring of s1 that can cover all chars in s2
public String minCoverageWindowSubstring(String s1, String s2) {
    // 记录t 以及 滑动窗口window中 字符与个数的映射关系
    HashMap<Character, Integer> windowMap = new HashMap<>();
    HashMap<Character, Integer> needMap = new HashMap<>();
    for (int i = 0; i < s2.length(); i++) {
        char c1 = s2.charAt(i);
        needMap.put(c1, needMap.getOrDefault(c1, 0) + 1);
    }
    // 双指针, 
    int left = 0, right = 0, valid = 0;
    // 用于更新满足的窗口window的长度,如果是len一直是MAX_VALUE，说明没有满足的串
    int len = Integer.MAX_VALUE;
    // 用于记录window串的起始位置，则返回 s[start, len]
    int start = 0;

    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        // 只要c是t中出现的字符就更新
        if (needMap.containsKey(c)) {
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
            // 更新c字符出现的次数，重复字符只会算一个valid，这个跟上面array算法中的区别
            if (windowMap.get(c).equals(needMap.get(c))) {
                valid++;
            }
        }
        // ----------------------------------
        // 收缩window的长度
        while (valid == needMap.size()) {
            // 更新并记录window的长度,以及window的起始位置start
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            //d 是将移出窗口的字符
            char d = s.charAt(left);
            left++;

            if (needMap.containsKey(d)) {
                if (windowMap.get(d).equals(needMap.get(d))) {
                    valid--;
                }
                windowMap.put(d, windowMap.get(d) - 1);
            }
        }
    } 
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

```

* Find all Anagrams  from a string of another string

```java
public List<Integer> findAnagrams(String s, String p) {
    // ========= 模板：定义相关数据结构，初始化工作============
    HashMap<Character, Integer> windowMap = new HashMap<>();
    HashMap<Character, Integer> needMap = new HashMap<>();
    for (int i = 0; i < p.length(); i++){
        char c1 = p.charAt(i);
        needMap.put(c1, needMap.getOrDefault(c1, 0) + 1);
    }
    int left = 0, right = 0, count = 0;
    
    ArrayList<Integer> res = new ArrayList<>();

    // ================== 模板：开始滑动窗口=====================
    while (right < s.length()) {

        // =========== 模板：向右滑动窗口，装填满足的字符到map中==========
        char c = s.charAt(right);
        right++;
        if (p_map.containsKey(c)) {
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
            if (windowMap.get(c).equals(needMap.get(c))) {
                count++;
            }
        }

        // =========== 根据题意：此时“有可能”出现满足条件的解 ==========
        // Notice the time of potention results and shrink window
        while (right - left == p.length()) {

            // ============= 根据题意：获取“真正”满足条件的解 =============
            if (count == needMap.size()){
                res.add(left);
            }

            // ========== 模板：左指针向右滑动，寻找下一个可行解/优化已知解======
            char d = s.charAt(left);
            left++;
            if (needMap.containsKey(d)) {
                if (windowMap.get(d).equals(needMap.get(d))) {
                    count--;
                }
                windowMap.put(d, windowMap.getOrDefault(d, 0) - 1);
            }
        }
    }
    return res;
}
```


---

# 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://coding.bea.ai/coding-patterns-and-template/3.-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.