# Sliding Window

## Template

Time O(n)

```python
int j = 0
for i in range(n):
    while j<n && array 不滿足條件
         j+=1
         拓寬條件
     if array 滿足條件
         看是不是最優的
     num[i]移出array
```

## 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

T: O(2n)

```python
def lengthOfLongestSubstring(self, s: str) -> int:
    record = set()
    res = 0
    i, j = 0, 0
    
    while j < len(s):
        while j < len(s) and s[j] not in record:
            record.add(s[j])
            j+=1
        res = max(res, j-i)
        record.remove(s[i])
        i+=1
    
    return res
```

T: O(n), S: O(n)

```python
def lengthOfLongestSubstring(self, s: str) -> int:
    record = collections.defaultdict(int)
    res = 0
    i = 0
    
    for j, c in enumerate(s):
        if c in record:
            i = max(i, record[c] + 1)
        res = max(res, j - i + 1)
        record[c] = j
    return res
```

## 340 Longest Substring with At Most K Distinct Characters

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

* 利用map的size判斷k的數量
* 若超過找出left most character 的index

```python
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
    dic = defaultdict(int)
    ans = 0
    i, j = 0, 0
    
    while j < len(s):
        dic[s[j]] = j
       
        if len(dic) > k:
            i = len(s)
            for idx in dic.values():
                i = min(i, idx)
            del dic[s[i]]
            i += 1
        ans = max(ans, j-i+1) 
        j +=1
        
    return ans
```

## 76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"

```python
def minWindow(self, s: str, t: str) -> str:
    dic = collections.Counter(t)
    record = collections.defaultdict(int)
    
    i, j = 0, 0
    ans = [-1, len(s)]
    
    for i in range(len(s)):
        ch = s[i]
        if ch not in dic: continue
        while j < len(s) and dic != record:
            ch_j = s[j]
            if ch_j in dic: record[ch_j] += 1
            j+=1 
        # 可能j走完但沒符合條件
        if dic == record and j-i < ans[1]-ans[0]:
            ans = [i,j]
        record[ch] -= 1
            
    return '' if ans[0] == -1 else s[ans[0]: ans[1]]
```

## 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 7, nums = \[2,3,1,2,4,3] Output: 2

* Init i=0 and left=0, iterate over nums

```python
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
    i, j = 0, 0
    n = len(nums)
    ans = n+1
    total = 0
    
    while i<n:
        while j<n and total < s:
            total += nums[j]
            j+=1
        if total >= s:
            ans = min(ans, j-i)
        total -= nums[i]
        i+=1
        
    return ans if ans !=n+1 else 0
```

## 862. Shortest Subarray with Sum at Least K

Return the **length** of the shortest, non-empty, contiguous subarray of `A` with sum at least `K`.

If there is no non-empty subarray with sum at least `K`, return `-1`.

1. 這題跟209的差異是num可能為負數
2. 用一個dequeue紀錄 sum and index, dequeue in increasing order by sum&#x20;
3. Update if we can find total - sum >= k, and kind updating to shorten the distant
4. [Explain](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O\(N\)-Using-Deque)

```python
def shortestSubarray(self, A: List[int], K: int) -> int:       
    q = [[-1, 0]] # [index, total]
    total = 0        
    ans = float('inf')

    for i, n in enumerate(A):
        total += n            
        while q and total - q[0][1] >= K:
            ans = min(ans, i - q[0][0])
            q.pop(0)
        
        while q and total <= q[-1][1]:
            q.pop()
        q.append([i, total])
        
    return ans if ans != float('inf') else -1
```

## 395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring **T** of a given string (consists of lowercase letters only) such that every character in **T** appears no less than k times.

* For loop n char, 代表每次check 只帶有 n char 的longest substring 的ans
* 2 counter: num of unique char and num of char more than k
* 只有在 count unique char == num of unique char && count of unique char == num of char more than k 才update&#x20;

O(26 \* n)

```python
def longestSubstring(self, s: str, k: int) -> int:
    res = 0
    # possible unique char in answers
    for i in range(1, 27):
        res = max(res, self.helper(s, k, i))
        
    return res

def helper(self, s, k, numOfUniqueTarget):
    i, j = 0, 0
    numOfUnique = 0
    numOfNoLessThanK = 0
    record = collections.defaultdict(int)
    res = 0
    
    while j < len(s):
        if numOfUnique <= numOfUniqueTarget:
            if record[s[j]] == 0:
                numOfUnique +=1
            record[s[j]] += 1
            if record[s[j]] == k:
                numOfNoLessThanK += 1
            j += 1
        else:
            if record[s[i]] == k:
                numOfNoLessThanK -= 1
            record[s[i]] -= 1
            if record[s[i]] == 0:
                numOfUnique -= 1
            i += 1
            
        
         # if we found a string where the number of unique chars equals our target
         # and all those chars are repeated at least K times then update max
        if numOfUnique == numOfUniqueTarget and numOfUnique == numOfNoLessThanK:
            res = max(res, j-i)
            
    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://netjimmy.gitbook.io/code-interview-note/array/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.