> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/array/sliding-window.md).

# 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
```