# Sliding window

## Intro

Window Sliding Technique is a computational technique that aims to reduce the use of nested loops and replace it with a single loop, thereby reducing the time complexity.

## [Leetcode 3] Longest Substring Without Repeating Characters

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

Example 1:

1 | Input: s = "abcabcbb" |

Example 2:

1 | Input: s = "bbbbb" |

Example 3:

1 | Input: s = "pwwkew" |

Constraints:

- 0 <= s.length <= 5 * 10^4
- s consists of English letters, digits, symbols and spaces.

Solution:

1 | class Solution: |

## [Leetcode 42] Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

1 | Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] |

Example 2:

1 | Input: height = [4,2,0,3,2,5] |

Constraints:

- n == height.length
- 1 <= n <= 2 * 10^4
- 0 <= height[i] <= 10^5

Solution:

1 | class Solution: |

## [Leetcode 209] Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

1 | Input: target = 7, nums = [2,3,1,2,4,3] |

Example 2:

1 | Input: target = 4, nums = [1,4,4] |

Example 3:

1 | Input: target = 11, nums = [1,1,1,1,1,1,1,1] |

Constraints:

- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Solution:

1 | class Solution: |

## [Leetcode 1004] Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.

Example 1:

1 | Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 |

Example 2:

1 | Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3 |

Constraints:

- 1 <= nums.length <= 105
- nums[i] is either 0 or 1.
- 0 <= k <= nums.length

Solution:

1 | class Solution: |

## [Leetcode 1456] Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’.

Example 1:

1 | Input: s = "abciiidef", k = 3 |

Example 2:

1 | Input: s = "aeiou", k = 2 |

Example 3:

1 | Input: s = "leetcode", k = 3 |

Constraints:

- 1 <= s.length <= 105
- s consists of lowercase English letters.
- 1 <= k <= s.length

Solution:

1 | class Solution: |

## [Leetcode 1493] Longest Subarray of 1’s After Deleting One Element

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array. Return 0 if there is no such subarray.

Example 1:

1 | Input: nums = [1,1,0,1] |

Example 2:

1 | Input: nums = [0,1,1,1,0,1,1,0,1] |

Example 3:

1 | Input: nums = [1,1,1] |

Constraints:

- 1 <= nums.length <= 105
- nums[i] is either 0 or 1

Solution:

1 | class Solution: |