# Sliding Window

* <https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/>
* <https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/>
* <https://leetcode.com/problems/replace-the-substring-for-balanced-string/>
* <https://leetcode.com/problems/max-consecutive-ones-iii/>
* <https://leetcode.com/problems/subarrays-with-k-different-integers/>
* <https://leetcode.com/problems/fruit-into-baskets/>
* <https://leetcode.com/problems/get-equal-substrings-within-budget/>
* <https://leetcode.com/problems/longest-repeating-character-replacement/>
* <https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/>
* <https://leetcode.com/problems/minimum-size-subarray-sum/>
* <https://leetcode.com/problems/sliding-window-maximum/>

#### [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

Use sliding window technique and store all characters in a int\[256] map.  Outer `while` loop use to expand window, inner `while` loop to shrink window. Update every time.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.isEmpty()) {
        return 0;
    }
    int res = 0;
    int[] map = new int[256];
    int L = 0, R = 0; 
    while (R < s.length()) {
        map[s.charAt(R)]++;
        while (map[s.charAt(R)] > 1) {
            map[s.charAt(L)]--;
            L++;
        }
        res = Math.max(res, R - L + 1);
        R++;
    }
    return res;
}
```

{% endtab %}

{% tab title="Python" %}

```python
def lengthOfLongestSubstring(self, s: str) -> int:
    dic = {}
    L = 0
    res = 0
    for R in range(len(s)):
        if s[R] not in dic:
            dic[s[R]] = 0
        dic[s[R]] += 1
        while dic[s[R]] > 1:
            lc = s[L]
            dic[lc] -= 1
            L += 1
        res = max(res, R - L + 1)
    return res
```

{% endtab %}
{% endtabs %}

[**159. Longest Substring with At Most Two Distinct Characters**](https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/)

Use a unique count variable to count how many unique characters are in the window. if `map[s.charAt(R)] == 1`, increase the count, when `map[s.charAt(L)] == 0`, decrease the count.

```java
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int res = 0;
        int[] map = new int[256];
        int L = 0, R = 0, count = 0; 
        while (R < s.length()) {
            map[s.charAt(R)]++;
            if (map[s.charAt(R)] == 1) {
                count++;
            }
            while (count > 2) {
                map[s.charAt(L)]--;
                if (map[s.charAt(L)] == 0) count--;
                L++;
            }
            res = Math.max(res, R - L + 1);
            R++;
        }
        return res;
    }
```

[**340. Longest Substring with At Most K Distinct Characters**](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/)

Change 2 above to k.

```java
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s == null || s.isEmpty()) {
        return 0;
    }
    int res = 0;
    int[] map = new int[256];
    int L = 0, R = 0, count = 0; 
    while (R < s.length()) {
        map[s.charAt(R)]++;
        if (map[s.charAt(R)] == 1) {
            count++;
        }
        while (count > k) {
            map[s.charAt(L)]--;
            if (map[s.charAt(L)] == 0) count--;
            L++;
        }
        res = Math.max(res, R - L + 1);
        R++;
    }
    return res;
}

```

#### [904. Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/)

{% tabs %}
{% tab title="Java" %}

```java
public int totalFruit(int[] tree) {
    int n = tree.length;
    int[] map = new int[n];
    int res = 0, count = 0;
    for (int L = 0, R = 0; R < n; R++) {
        int rc = tree[R];
        if (++map[rc] == 1) {
            count++;
        }
        while (count > 2) {
            int lc = tree[L++];
            if (--map[lc] == 0) {
                count--;
            }
        }
        res = Math.max(res, R - L + 1);
    }
    return res;
}
```

{% endtab %}

{% tab title="Python" %}

```python
def totalFruit(self, tree: List[int]) -> int:
    dic = {}
    L, R, n, count, res = 0, 0, len(tree), 0, 0;
    while R < n:
        rc = tree[R]
        if rc not in dic:
            dic[rc] = 0;
        dic[rc] += 1
        if dic[rc] == 1:
            count += 1
        while count > 2:
            lc = tree[L]
            dic[lc] -= 1
            if dic[lc] == 0:
                count -= 1
            L += 1
        res = max(res, R - L + 1)
        R += 1
    return res
```

{% endtab %}
{% endtabs %}

[**76. Minimum Window Substring**](https://leetcode.com/problems/minimum-window-substring/)

Use sliding window to keep track of the records. HashMap to record char and its count. Preprocess target string with map. Use char count == 0 and length count == t.length()  to represent when all records are found

String:  ADOBECODEBANC

&#x20;            j       i

* If (map.contains(nums\[i]) reduce count of that char, when count >=0 , foundCount++;
* While foundCount == t.length(). Update result. And reduce window size by moving j.
* When map.contains(nums\[j]), count of char ++, when map.get(char\[j]) > 1, foundCount--;  and j++;&#x20;

```java
    public String minWindow(String s, String t) {
        int[] map = new int[256];
        for (char c : t.toCharArray()) {
            map[c]++;
        }
        int min = Integer.MAX_VALUE, minLeft = 0;
        int L = 0, R = 0, count = 0; 
        while (R < s.length()) {
            if (map[s.charAt(R)]-- > 0) {
                count++;
            }
            while (count == t.length()) {
                if (R - L + 1 < min) {
                    min = R - L + 1;
                    minLeft = L;
                }
                if (map[s.charAt(L)]++ >= 0) {
                    count--;
                }
                L++;
            }
            R++;
        }
        return min == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + min);
    }
```

[**438. Find All Anagrams in a String**](https://leetcode.com/problems/find-all-anagrams-in-a-string/)

* **先做一个Map来存P里面的character数，用一个count来存找到了多少个char**
* **右边一直走，把碰到的c在map里减少一个，每减少一个 (map\[R]-- > 0) 说明找到一个p中的字符，count++**
* **在R - L + 1 == p.length()的情况下，说明找到了一个和P长度一样的Window，这时候看count也等于p.length()的话，说明是一个解**
* **左边if (map\[L]++ >= 0) count--;  left++;**

```java
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int[] map = new int[256];
        for (int c : p.toCharArray()) {
            map[c]++;
        }
        int L = 0, R = 0, count = 0;
        while (R < s.length()) {
            if (map[s.charAt(R)]-- > 0) {
                count++;
            }
            while (R - L + 1 == p.length()) {
                if (count == p.length()) {
                    result.add(L);
                }
                if (map[s.charAt(L)]++ >= 0) {
                    count--;   
                }
                L++;
            }
            R++;
        }
        return result;
    }
```

[1456. Maximum Number of Vowels in a Substring of Given Length](https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/)

```cpp
int maxVowels(string s, int k) {
    std::string vowels = "aeiou";
    int vCount = 0, res = 0;
    int left = 0;
    for (int right = 0; right < s.size(); ++right) {
        char c = s.at(right);
        if (vowels.find(c) != std::string::npos) {
            vCount++;
        }
        if (right - left >= k) {
            char lc = s.at(left);
            if (vowels.find(lc) != std::string::npos) {
                --vCount;
            }
            left++;
        }
        res = max(res, vCount);
    }
    return res;
}
```

[**395. Longest Substring with At Least K Repeating Characters**](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/)

求最长的，每个Char重复至少K次的substring。这个就不能按照普通的SlidingWindow来做，因为不仅要统计每个char重复的次数，而且要看有几个char达到了要求。而且要求是一直在变的。从1到26个char都有可能。

N从1到26循环，每次都要找一下有几个字符，并且字符个数 >= k而且字符的个数和 >= k字符个数相等。在这种情况下更新长度

```java
    public int longestSubstring(String s, int k) {
        int max = 0;
        for (int i = 1; i <= 26; i++) {
            max = Math.max(max, helper(s, k, i));
        }
        return max;
    }
  
    private int helper(String s, int k, int uniqueLimit) { 
        int[] map = new int[256];
        int count = 0;
        int numNoLessThanK = 0;
        int max = 0;
        for (int i = 0, left = 0; i < s.length(); i++) {
            if (map[s.charAt(i)]++ == 0) count++;
            if (map[s.charAt(i)] == k) numNoLessThanK++;
            while (count > uniqueLimit) {
                if (map[s.charAt(left)]-- == k) numNoLessThanK--;
                if (map[s.charAt(left)] == 0) count--;
                left++;
            }
            if (count == uniqueLimit && count == numNoLessThanK) {
                max = Math.max(max, i - left + 1);
            }
        }
        return max;
    }
```

#### [992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/)

Use sliding winder to get the count of K different elements. Minus the result by K - 1 different elements. That is exactly K different elements.

```java
public int subarraysWithKDistinct(int[] A, int K) {
    return helper(A, K) - helper(A, K - 1);
}

private int helper(int[] A, int K) {
    int n = A.length;
    int[] map = new int[n + 1];
    int count = 0, res = 0;
    for (int i = 0, left = 0; i < n; i++) {
        if (++map[A[i]] == 1) {
            count++;
        }
        while (count > K) {
            if (--map[A[left++]] == 0) {
                count--;
            }
        }
        res += i - left + 1;
    }
    return res;
}
```

713\. Subarray Product Less Than K

485\. Max Consecutive Ones

#### [209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)

```java
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int L = 0, R = 0;
        long sum = 0;
        int res = Integer.MAX_VALUE;
        while (R < nums.length) {
            sum += nums[R];
            while (sum >= s) {
                res = Math.min(res, R - L + 1);
                sum -= nums[L++];
            }
            R++;
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
```

&#x20; \ <br>

[**1100. Find K-Length Substrings With No Repeated Characters**](https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/)\ <br>

#### [1423. Maximum Points You Can Obtain from Cards](https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/)

This problem is hard to interpret. It means you have to select k cards from begin or end or both. This is actually a two pointer + sliding window problem. `LSum` represents the sum on left side, then slide to the left, `RSum` is the sum on the right side. `LSum + RSum` is one of the result.

![https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/discuss/597825/Simple-Clean-Intuitive-Explanation-with-Visualization](/files/-ME6A3r0ws8fTH6XaJRS)

```java
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int lsum = 0, rsum = 0;
        for (int i = 0; i < k; i++) {
            lsum += cardPoints[i];
        }
        int res = lsum + rsum;
        for (int i = 0; i < k; i++) {
            lsum -= cardPoints[k - i - 1];
            rsum += cardPoints[n - i - 1];
            res = Math.max(res, lsum + rsum);
        }
        return res;
    }
```

####

#### **30. Substring with Concatenation of All Words**

1. **Get all words into a set of string combinations by using backtracking. Slide window and compare substring. First step took very long since backtracking takes O(k^2) where k is size of words** &#x20;
2. [**Slide window.**](https://leetcode.windliang.cc/leetCode-30-Substring-with-Concatenation-of-All-Words.html)&#x20;
   1. **Save target words and their count to a target map.**
   2. **Use i to control left bound, j as right bound, to slide window. J is the index in words\[], which also control length**
   3. **Create a new map (“seen”) every move, count the words between i and j. If there are unseen words, break. Otherwise put seen words in the “seen” map.**&#x20;
   4. **就把该单词存到新的 HashMap 中，并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ，如果大了，就代表该子串不是我们要找的，接着判断下一个子串就可以了。如果不大于，那么我们接着判断下一个单词的情况。子串扫描结束，如果子串的全部单词都符合，那么该子串就是我们找的其中一个。**&#x20;
   5. **T：假设 s 的长度是 n，words 里有 m 个单词，那么时间复杂度就是 O（n \* m）. S：两个 HashMap，假设 words 里有 m 个单词，就是 O（m）。**
3. [**Optimized Slide window**](https://leetcode.windliang.cc/leetCode-30-Substring-with-Concatenation-of-All-Words.html)<br>

[**567. Permutation in String**](https://leetcode.com/problems/permutation-in-string/)

**如果S的长度小于T说明不可能，Return false**

**做两个Map，把S， T都count一下。**

**i来循环T，并且update 这个window的字符。看两个map是不是相等：**

```java
```

```java
```

&#x20;       **int len = s1.length();**

&#x20;       **for (int i = 0; i + len < s2.length(); i++) {**

&#x20;           **if (isSame(s1map, s2map)) return true;**

&#x20;           **s2map\[s2.charAt(i + len) - 'a']++;**

&#x20;           **s2map\[s2.charAt(i) - 'a']--;**

&#x20;       **}**

&#x20;       **return isSame(s1map, s2map);**

Number of Substrings Containing All Three Characters

Count Number of Nice Subarrays

Replace the Substring for Balanced String

Max Consecutive Ones III

Binary Subarrays With Sum

Subarrays with K Different Integers

Fruit Into Baskets

Shortest Subarray with Sum at Least K

Minimum Size Subarray Sum

[424. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)

```typescript
function characterReplacement(s: string, k: number): number {
    const freq: Record<string, number> = {};
    let maxCount = 0;  // max frequency of a single char in current window
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const rightChar = s[right];
        freq[rightChar] = (freq[rightChar] || 0) + 1;

        maxCount = Math.max(maxCount, freq[rightChar]);

        // If more than k chars need to be replaced, shrink window
        while ((right - left + 1) - maxCount > k) {
            const leftChar = s[left];
            freq[leftChar]--;
            left++;
            // Note: no need to update maxCount here because it only ever grows or stays the same,
            // which is fine for correctness in this problem.
        }

        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

```

[2962. Count Subarrays Where Max Element Appears at Least K Times](https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/)

```typescript
function countSubarrays(nums: number[], k: number): number {
  const maxElement = Math.max(...nums);
  let left = 0;
  let ans = 0;
  let maxElementInWindow = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === maxElement) {
      maxElementInWindow++;
    }

    while (maxElementInWindow >= k) {
      if (nums[left] === maxElement) {
        maxElementInWindow--;
      }
      left++;
    }

    ans += left;
  }

  return ans;
};
```

[**2067. Number of Equal Count Substrings**](https://leetcode.com/problems/number-of-equal-count-substrings/)

```cpp
class Solution {
public:
int equalCountSubstrings(string s, int count) {
        int ans = 0;
        int n = s.size();

        for (int distinctTarget = 1; distinctTarget <= 26; distinctTarget++) {
            vector<int> freq(26, 0);
            int left = 0, right = 0;
            int unique = 0;        // number of unique chars in window
            int countAtTarget = 0; // chars whose frequency == count

            while (right < n) {
                int idx = s[right] - 'a';
                freq[idx]++;
                if (freq[idx] == 1) unique++;
                if (freq[idx] == count) countAtTarget++;

                while (unique > distinctTarget || (right - left + 1) > distinctTarget * count) {
                    int leftIdx = s[left] - 'a';
                    if (freq[leftIdx] == count) countAtTarget--;
                    freq[leftIdx]--;
                    if (freq[leftIdx] == 0) unique--;
                    left++;
                }

                if (unique == distinctTarget && countAtTarget == distinctTarget
                    && (right - left + 1) == distinctTarget * count) {
                    ans++;
                }
                right++;
            }
        }
        return ans;
    }
};
```

[2831. Find the Longest Equal Subarray](https://leetcode.com/problems/find-the-longest-equal-subarray/)

```cpp
class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> countMap;
        int left = 0;
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            countMap[nums[i]].push_back(i);
        }
        for (const auto& [val, indicies] : countMap) {
            int left = 0;
            for (int right = 0; right < indicies.size(); ++right) {
                // indicies[right] - indicies[left] - (right - left) <> k
                while (indicies[right] - indicies[left] - (right - left) > k) {
                    ++left;
                }
                res = max(res, right - left + 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://howardyangemail.gitbook.io/decode-leetcode/string/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.