The sliding window is a problem-solving technique that’s designed to transform two nested loops into a single loop. It applies to arrays or lists. These problems are painless to solve using a brute force approach in O(n²) or O(n³). However, the sliding window technique can reduce the time complexity to O(n).

## Sliding Window Algorithm Definition

Sliding window algorithm is a problem solving technique that transforms two nested loops into one loop. It can reduce the time complexity to O(n).

## What Is the Sliding Window Algorithm?

The basic idea behind the sliding window technique is to transform two nested loops into a single loop. Below are some fundamental clues to identify sliding window algorithm problems:

- The problem will be based on an array, list or string type of data structure.
- It will ask to find subranges in that array to give the longest, shortest or target values of a string.
- Its concept is mainly based on ideas like the longest sequence or shortest sequence of something that satisfies a given condition perfectly.

Let's say that if you have an array like below:

A sliding window of size three** **would run over it like below:

I believe the sliding window algorithm is more of a technique than an algorithm since it can be employed in many algorithms.

## How to Solve a Problem With the Sliding Window Algorithm

Below is the basic step to solve problems related to the sliding window technique:

- Use a HashMap or dictionary to count a specific array input and increase the window toward the right using an outer loop.
- Take one inside a loop to reduce the window side by sliding towards the right. This loop will be very short.
- Store the current maximum or minimum window size or count based on the problem statement.

Example of sliding to find the largest sum of five consecutive elements.

`[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]`

## Sliding Window Algorithm Examples With Solutions

There are many problem statements of sliding window techniques. We’ll review the following:

### 1. Maximum Sum Subarray of Size K

Given an array of positive integers and a positive number`k`

, find the maximum sum of any contiguous subarray of size `k`

.

```
Input: [3, 5, 2, 1, 7], k=2
Output: 8
```

The subarray `[1, 7]`

is the sum of the maximum sum.

#### Solution

```
def getMaxSum(arr, k):
maxSum = 0
windowSum = 0
start = 0
for i in range(len(arr)):
windowSum += arr[i]
if ((i - start + 1) == k):
maxSum = max(maxSum, windowSum)
windowSum -= arr[start]
start += 1
return maxSum
```

### 2. Count Occurrences of Anagram

Given a word and a text, return the count of occurrences of the anagrams of the word in the text.

```
Input: text = gotxxotgxdogt, word = got
Output : 3
```

Words “got,” “otg” and “ogt” are anagrams of “got.”

**Solution**

```
def countAnagram(text, word):
w = len(word)
count = 0
ana = ''
d = {}
for i in range(w):
ana += text[i]
if isAnagram(ana, word):
count += 1
for i in range(1, len(text)):
ana = ana[1:] + text[i]
if ana not in d and isAnagram(ana, word):
count += 1
d[ana] = 0
d[ana] = 0
return count
```

Is Anagram Util:

```
def isAnagram(s, word):
if len(s) != len(word):
return False
d = [0] * 26
for c in s:
d[ord(c) - ord('a')] = 1
for c in word:
if d[ord(c) - ord('a')] == 0:
return False
return True
```

Here’s another solution with a different approach:

```
def getCountOccurances(text, word):
wHeap = [0] * 26
textHeap = [0] * 26
start = 0
count = 0
for c in word:
wHeap[ord(c) - ord('a')] += 1
for i in range(len(text)):
textHeap[ord(text[i]) - ord('a')] += 1
if (i - start + 1) == len(word):
if textHeap == wHeap:
count += 1
textHeap[ord(text[start]) - ord('a')] -= 1
start += 1
return count
```

### 3. Difference Between the Maximum and Minimum Average of all K-Length Continuous Subarrays

```
Input: arr[ ] = {3, 8, 9, 15}, K = 2
Output: 6.5
```

All subarrays of length 2 are `{3, 8}`

, `{8, 9}`

, `{9, 15}`

and their averages are `(3+8)/2 = 5.5, (8+9)/2 = 8.5`

, and `(9+15)/2 = 12.0`

respectively.

Therefore, the difference between the `maximum(=12.0)`

and `minimum(=5.5)`

is `12.0 -5.5 = 6.5`

.

#### Solution

```
def getMinMaxDiff(arr, k):
n = len(arr)
if k > n:
return -1
min_avg = float('inf')
max_avg = float('-inf')
window_sum = sum(arr[:k])
for i in range(k, n):
current_avg = window_sum / k
min_avg = min(min_avg, current_avg)
max_avg = max(max_avg, current_avg)
window_sum -= arr[i - k]
window_sum += arr[i]
last_avg = window_sum / k
min_avg = min(min_avg, last_avg)
max_avg = max(max_avg, last_avg)
difference = max_avg - min_avg
return difference
# Test case
arr = [3, 8, 9, 15]
k = 2
result = getMinMaxDiff(arr, k)
print(result) # Output: 6.5
```

### 4. Find the Longest Substring of a String Containing ‘K’ Distinct Characters

```
Input: s = 'abcbdbdbbdcdabd'
k = 2
Output: bdbdbbd
```

#### Solution

```
def getLongest(s, k):
high = 0
windows = set()
freq = [0] * 128
low = 0
end = 0
start = 0
while high < len(s):
windows.add(s[high])
freq[ord(s[high])] += 1
while len(windows) > k:
freq[ord(s[low])] -= 1
if freq[ord(s[low])] == 0:
windows.remove(s[low])
low += 1
if end - start < high - low:
end = high
start = low
high += 1
return s[start:end + 1]
```

### 5. Find Duplicates Within a Range ‘K’ in an Array

```
Input: nums = [5, 6, 8, 2, 4, 6, 9]
k = 2
Ouput: False
```

#### Solution

```
def getDuplicates(nums, k):
d = {}
count = 0
for i in range(len(nums)):
if nums[i] in d and i - d[nums[i]] <= k:
return True
else:
d[nums[i]] = i
return False
```

### 6. Find Minimum Sum SubArray of Size K

```
Input: arr = [10, 4, 2, 5, 6, 3, 8, 1]
k = 3
Output: 11
```

#### Solution

```
def getMinSum(arr, k):
currSum = 0
minSum = float("inf")
start = 0
for i in range(len(arr)):
currSum += arr[i]
if (i - start + 1 == k):
minSum = min(minSum, currSum)
currSum -= arr[start]
start += 1
return minSum
```

### 7. Length of the Longest Substring That Doesn’t Contain Any Vowels

```
Input: s = "codeforintelligents"
Output: 3
Explanation: 'nts' is the longest substring that doesn't contain any vowels.
```

#### Solution

```
def getLongestSubstring(s):
vowels = ['a', 'e', 'i', 'o', 'u']
result = ""
maxResult = ""
for i in range(len(s)):
if s[i] not in vowels:
result += s[i]
print(result)
if len(result) > len(maxResult):
maxResult = result
else:
result = ""
return len(maxResult)
```

### 8. Count Negative Elements Present in Every K-Length Subarray

```
Input: arr = [-1, 2, -2, 3, 5, -7, -5], K = 3
Output: 2, 1, 1, 1, 2
```

#### Solution

```
def getCountNegatives(arr, k):
lst = []
start = 0
count = 0
for i in range(len(arr)):
if arr[i] < 0:
count += 1
if (i - start + 1 == k):
lst.append(count)
if arr[start] < 0:
count -= 1
start += 1
return lst
```

### 9. Minimum Size Subarray Sum

```
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint
```

#### Solution

```
def minSubArrayLen(target, nums):
currSum = 0
start = 0
count = 0
minCount = float("inf")
for i in range(len(nums)):
currSum += nums[i]
while currSum >= target:
minCount = min(minCount, i - start + 1)
currSum -= nums[start]
start += 1
if minCount == float("inf"):
return 0
return minCount
```

### 10. Longest Repeating Character Replacement

You are given a string s and an integer `k`

. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most `k`

times.

```
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
```

#### Solution

```
def characterReplacement(self, s, k):
freq = {}
maxRepeatLetterCount = 0
windowStart = 0
maxLength = 0
for i in range(len(s)):
if s[i] not in freq:
freq[s[i]]= 0
freq[s[i]] += 1
maxRepeatLetterCount = max(maxRepeatLetterCount, freq[s[i]])
if (i - windowStart + 1 - maxRepeatLetterCount) > k:
freq[s[windowStart]] -= 1
windowStart += 1
maxLength = max(maxLength, i-windowStart + 1)
return maxLength
```

### 11. Count Distinct Absolute Values in a Sorted Array

```
Input: { -1, -1, 0, 1, 1, 1 }
Output: The total number of distinct absolute values is 2 (0 and 1)
```

#### Solution

```
def getCountDistinct(arr):
count = 0
d = {}
for item in arr:
if item >= 0 and item not in d:
d[item] = 1
count += 1
return count
```

### 12. Permutation in String

Given two strings `s1`

and `s2`

, return true if `s2`

contains a permutation of `s1`

, or false otherwise.

In other words, return true if one of `s1`

’s permutations is the substring of `s2`

.

```
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
```

#### Solution

```
def checkInclusion(self, s1, s2):
numbers = [0]*26
numbers2 = [0]*26
for c in s1:
numbers[ord(c) - ord('a')] += 1
for index in range(0, len(s2)):
numbers2[ord(s2[index]) - ord('a')] += 1
if index >= len(s1) - 1:
if numbers == numbers2:
return True
numbers2[ord(s2[index - len(s1) + 1]) - ord('a')] -= 1
return False
```

### 13. Find All Anagrams in a String

```
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
```

**Solution**

```
def findAnagrams(s, p):
target = [0] * 26
result = []
count = [0] * 26
start = 0
for c in p:
target[ord(c) - ord('a')] += 1
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
if i - start == len(p):
count[ord(s[start]) - ord('a')] -= 1
start += 1
if count == target:
result.append(start)
return result
```

### 14. Maximum Average Subarray I

You are given an integer array of nums consisting of n elements and an integer `k`

.

Find a contiguous subarray whose length is equal to `k`

that has the maximum average value and return this value. Any answer with a calculation error less than `10–5`

will be accepted.

```
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
```

#### Solution

```
def findMaxAverage(self, nums, k):
st = 0
max_sum = float('-inf')
win_sum = 0.0
for i in range(len(nums)):
win_sum += nums[i]
if i >= k-1:
max_sum = max(win_sum, max_sum)
win_sum -= nums[st]
st += 1
return max_sum/k
```

**15. K Radius Subarray Averages**

Build and return an array `avgs`

of length `n`

where `avgs[i]`

is the k-radius average for the subarray centered at index `i`

.

```
Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
```

#### Solution

```
def getAverages(self, nums, k):
if k == 0:
return nums
n = len(nums)
ans = [-1] * n
prefSum = [0] * n
for i in range(0, n):
if i == 0:
prefSum[0] = nums[i]
else:
prefSum[i] = prefSum[i-1] + nums[i]
for i in range(k, n-k):
if i-k-1 < 0:
ans[i] = (prefSum[i + k])//(2*k + 1)
else:
ans[i] = (prefSum[i + k] - prefSum[i - k - 1])//(2*k + 1)
return ans
```

### 18. Substrings of Size Three With Distinct Characters

A string is good if there are no repeated characters.

Given a string `s`

, return the* *number of good substrings of length three in `s`

.

If there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

```
Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".
The only good substring of length 3 is "xyz".
```

#### Solution

```
class Solution(object):
def countGoodSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
k = 3
if k > len(s):
return 0
freq = {}
count = 0
start = 0
for i in range(len(s)):
if s[i] not in freq:
freq[s[i]] = 0
freq[s[i]] += 1
if i >= k - 1:
if len(freq) == k:
count += 1
freq[s[start]] -= 1
if freq[s[start]] == 0:
del freq[s[start]]
start += 1
return count
```

### 19. Frequency of the Most Frequent Element

The frequency of an element is the number of times it occurs in an array.

You are given an integer array `nums`

and an integer `k`

. In one operation, you can choose an index of `nums`

and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most `k`

operations.

```
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.
```

#### Solution

```
class Solution(object):
def maxFrequency(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
len_nums = len(nums)
nums.sort()
max_freq = 1
freq = 1
left = 0
ops = k
for right in range(1, len_nums):
ops -= (nums[right] - nums[right - 1]) * freq
freq += 1
if ops >= 0:
max_freq = max(max_freq, freq)
else:
while ops < 0:
ops += nums[right] - nums[left]
left += 1
freq -= 1
return max_freq
```

### 20. Maximum Erasure Value

You are given an array of positive integers `nums`

and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array `b`

is called to be a subarray if it forms a contiguous subsequence of `a`

that is if it is equal to `a[l], a[l+1],…, a[r]`

for some `(l,r)`

.

```
Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].
```

#### Solution

```
class Solution(object):
def maximumUniqueSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
m = {}
final = 0
summ = 0
l = 0
for i in range(len(nums)):
if nums[i] in m:
index = m[nums[i]]
while l <= index:
del m[nums[l]]
summ -= nums[l]
l += 1
m[nums[i]] = i
summ += nums[i]
final = max(final, summ)
return final
```

**21. Maximum Number of Occurrences of a Substring**

Given a string `s`

, return the maximum number of occurrences of any substring under the following rules:

- The number of unique characters in the substring must be less than or equal to maxLetters.
- The substring size must be between
`minSize`

and`maxSize`

inclusive.

```
Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).
```

**Solution**

```
class Solution(object):
def maxFreq(self, s, maxLetters, minSize, maxSize):
"""
:type s: str
:type maxLetters: int
:type minSize: int
:type maxSize: int
:rtype: int
"""
cnt = {}
res= 0
for i in range(0,len(s)-minSize+1):
sub = s[i:i + minSize]
if len(set(sub)) <= maxLetters:
if sub not in cnt:
cnt[sub] = 0
cnt[sub] += 1
res = max(res, cnt[sub])
return res
```

### 22. Number of Subarrays of Size K and Average Greater than or Equal to Threshold

Given an array of integers `arr`

and two integers `k`

and threshold.

Return the number of subarrays of size `k`

and average greater than or equal to a threshold.

```
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).
```

**Solution**

```
class Solution(object):
def numOfSubarrays(self, arr, k, threshold):
"""
:type arr: List[int]
:type k: int
:type threshold: int
:rtype: int
"""
start = 0
windowSum = 0
count = 0
for windowEnd in range(len(arr)):
windowSum += arr[windowEnd]
if windowEnd >= k - 1:
if (windowSum/k) >= threshold:
count+=1
windowSum -=arr[start]
start += 1
return count
```

**23. Number of Substrings Containing All Three Characters**

Given a string s consisting only of characters *a*, *b* and *c*.

Return the number of substrings containing at least one occurrence of all these characters *a*, *b* and *c*.

```
Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again)
```

#### Solution

```
class Solution(object):
def numberOfSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
count, left = 0, 0
map = {x:0 for x in "abc"}
for right in range(0,len(s)):
map[s[right]] += 1
while map["a"] and map["b"] and map["c"]:
map[s[left]] -= 1
left += 1
count += left
return count
```

**24. Maximum Points You Can Obtain from Cards**

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array `cardPoints`

.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array `cardPoints`

and the integer k, return the maximum score you can obtain.

```
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.
```

**Solution**

```
class Solution(object):
def maxScore(self, cardPoints, k):
"""
:type cardPoints: List[int]
:type k: int
:rtype: int
"""
best = score = sum(cardPoints[:k])
for i in range(1, k+1):
score = score - cardPoints[k-i] + cardPoints[-i]
best = score if score > best else best
return best
```

**25. Longest Continuous Subarray With Absolute Diff Less Than or Equal to**

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to the limit*.*

```
Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.
```

**Solution**

```
class Solution(object):
def longestSubarray(self, nums, limit):
"""
:type nums: List[int]
:type limit: int
:rtype: int
"""
if not nums:
return 0
if len(nums) == 1:
return 1
l = 0
r = 1
cur_mx = nums[0]
cur_mn = nums[0]
max_l = 1
while l <= r and r < len(nums):
cur_mx = max(cur_mx, nums[r])
cur_mn = min(cur_mn, nums[r])
if cur_mx - cur_mn <= limit:
max_l = max(max_l, r - l + 1)
else:
if nums[l] == cur_mx:
cur_mx = max(nums[l + 1:r + 1])
if nums[l] == cur_mn:
cur_mn = min(nums[l + 1:r + 1])
l += 1
r += 1
return max_l
```

### 27. 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, u).

```
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.
```

**Solution**

```
class Solution(object):
def maxVowels(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
vowels = ['a','e','i','o','u']
ans = 0
win = ''
v = 0
for char in range(k):
win += s[char]
if s[char] in vowels:
v+=1
ans = max(ans,v)
for char in range(len(s)-k):
win += s[char+k]
if s[char] in vowels:
v-=1
if s[char+k] in vowels:
v+=1
ans=max(ans,v)
return ans
```

Another approach:

```
def getMaxVowels(s, k):
vowels = ['a', 'e', 'i', 'o', 'u']
temp = ''
isVowel = True
start = 0
maxCount = 0
for i in range(len(s)):
if s[i] in vowels:
temp += s[i]
else:
isVowel = False
if (i - start + 1 == k or isVowel == False):
maxCount = max(maxCount, len(temp))
if isVowel == False:
temp = ''
isVowel = True
else:
temp = temp[1:]
start += 1
return maxCount
```

**28. Find Two Non-overlapping Subarrays Each With Target Sum**

Given an array of integers arr and an integer target.

You have to find two non-overlapping subarrays of arr each with a sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two subarrays is minimum.

Return the minimum sum of the lengths of the two required subarrays, or return -1 if you cannot find such two subarrays.

```
Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2
```

**Solution**

```
class Solution(object):
def minSumOfLengths(self, arr, target):
"""
:type arr: List[int]
:type target: int
:rtype: int
"""
INF = len(arr) + 1
best_at_i = [INF]*len(arr)
best = INF
curr_sum = 0
left = 0
for right in range(len(arr)):
curr_sum += arr[right]
while curr_sum > target and left <= right:
curr_sum -= arr[left]
left += 1
if curr_sum == target:
best = min(best, best_at_i[left-1] + right - left + 1)
best_at_i[right] = min(best_at_i[right-1], right - left + 1)
else:
best_at_i[right] = best_at_i[right-1]
if best == INF:
return -1
return best
```

**29. Longest Subarray of 1’s After Deleting One Element**

Given 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.

```
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.
```

**Solution**

```
class Solution(object):
def longestSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
windowStart = 0
hashmap = {x: 0 for x in nums}
max_length = 0
if 0 not in hashmap.keys():
return len(nums) - 1
for windowEnd in range(len(nums)):
hashmap[nums[windowEnd]] += 1
if hashmap[0] > 1:
hashmap[nums[windowStart]] -= 1
windowStart += 1
max_length = max(max_length, windowEnd - windowStart)
return (max_length)
```

**30. Minimum Operations to Reduce X to Zero**

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.

```
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
```

#### Solution

```
class Solution(object):
def minOperations(self, nums, x):
"""
:type nums: List[int]
:type x: int
:rtype: int
"""
S = sum(nums)
left = right = curr = 0
ans = -1
while right<len(nums):
curr += nums[right]
right+=1
while left<len(nums) and curr>S-x:
curr-=nums[left]
left+=1
if curr == S-x:
ans = max(ans,right-left)
return len(nums) - ans if ans!=-1 else ans
```

**31. Get Equal Substrings Within Budget**

You are also given an integer `maxCost`

.

Return the maximum length of a substring of `s`

that can be changed to be the same as the corresponding substring of `t`

with a cost less than or equal to `maxCost`

.

If there is no substring from `s`

that can be changed to its corresponding substring from `t`

, return 0.

```
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
```

**Solution**

```
class Solution(object):
def equalSubstring(self, s, t, maxCost):
"""
:type s: str
:type t: str
:type maxCost: int
:rtype: int
"""
diff = [abs(ord(s[i]) - ord(t[i])) for i in range(len(s))]
summ = 0
low = length = 0
for i in range(len(s)):
summ += diff[i]
while low < i and summ > maxCost:
summ -= diff[low]
low += 1
if summ <= maxCost:
length = max(length, i-low+1)
return length
```

**32. Grumpy Bookstore Owner**

There is a bookstore owner that has a store open for `n`

minutes. Every minute, some number of customers enter the store. You are given an integer array of customers of length `n`

where `customers[i]`

is the number of the customer that enters the store at the start of the `ith`

minute and all those customers leave after the end of that minute.

For some minutes, the bookstore owner is grumpy. You are given a binary array `grumpy`

where `grumpy[i]`

is `1`

if the bookstore owner is grumpy during the `ith`

minute, and is 0 otherwise.

When the bookstore owner is grumpy, the customers during that minute aren’t satisfied, otherwise, they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for consecutive minutes but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

```
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
```

**Solution**

```
class Solution(object):
def maxSatisfied(self, customers, grumpy, minutes):
"""
:type customers: List[int]
:type grumpy: List[int]
:type minutes: int
:rtype: int
"""
n = len(customers)
res = 0
for i in range(n):
if grumpy[i] == 0:
res += customers[i]
sum1 = 0
for i in range(minutes):
if grumpy[i] == 1:
sum1 += customers[i]
result = sum1
for r in range(minutes, n):
if grumpy[r] == 1:
sum1 += customers[r]
if grumpy[r - minutes] == 1:
sum1 -= customers[r - minutes]
result = max(sum1, result)
return res + result
```

### 33. Max Consecutive Ones III

Given 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.

```
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
```

**Solution**

```
class Solution(object):
def longestOnes(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
start, end, n, max_consecutive = 0, 0, len(nums), 0
while end < n:
if nums[end] == 0:
if k > 0:
k -= 1
else:
max_consecutive = max(max_consecutive, end - start)
if nums[start] == 0:
k += 1
start += 1
continue
end += 1
```

**34. Binary Subarrays With Sum**

Given binary array `nums`

and an integer `goal`

, return the number of non-empty subarrays with a sum `goal`

. A subarray is a contiguous part of the array.

```
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
```

**Solution**

```
class Solution(object):
def numSubarraysWithSum(self, nums, goal):
"""
:type nums: List[int]
:type goal: int
:rtype: int
"""
cumSum = 0
result = 0
hashMap = {0:1}
for x in nums:
cumSum += x
val = cumSum - goal
if (val) in hashMap:
result += hashMap[val]
hashMap[cumSum] = hashMap.get(cumSum, 0) + 1
return result
```

### 35. Maximum Length of Repeated Subarray

Given two integer arrays `nums1`

and `nums2`

, return the maximum length of a subarray that appears in both arrays.

```
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].
```

**Solution**

```
class Solution(object):
def findLength(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""
nums2_str = ''.join([chr(x) for x in nums2])
max_str = ''
res = 0
for num in nums1:
max_str += chr(num)
if max_str in nums2_str:
res = max(res,len(max_str))
else:
max_str = max_str[1:]
return res
```

**36. Longest Turbulent Subarray**

Given an integer array `arr`

, return the length of a maximum size turbulent subarray of `arr`

.

A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

```
Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
```

**Solution**

```
class Solution(object):
def maxTurbulenceSize(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
n = len(arr)
ans = 1
anchor = 0
for i in range(1, n):
c = cmp(arr[i-1], arr[i])
if c == 0:
anchor = i
elif i == n - 1 or c * cmp(arr[i], arr[i+1]) != -1:
ans = max(ans, i - anchor + 1)
anchor = i
return ans
```

**37. Longest Substring Of All Vowels in Order**

Given a string word consisting of English vowels, return the length of the longest beautiful substring of a word. If no such substring exists, return 0.

A substring is a contiguous sequence of characters in a string.

```
Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
Output: 13
Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.
```

#### Solution

```
class Solution(object):
def longestBeautifulSubstring(self, word):
"""
:type word: str
:rtype: int
"""
res = 0
i = 0
seen = set()
for j in range(0,len(word)):
if j > 0 and word[j] < word[j-1]:
seen = set()
i = j
seen.add(word[j])
if len(seen) == 5:
res = max(res,j-i+1)
return res
```

**38. Fruit Into Baskets**

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array `fruits`

where `fruits[i]`

is the type of fruit the `ith`

tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

- You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
- Starting from any tree of your choice, you must pick exactly
- Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer `array`

, return the maximum number of fruits you can pick.

```
Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.
```

#### Solution

```
class Solution(object):
def totalFruit(self, fruits):
"""
:type fruits: List[int]
:rtype: int
"""
length = len(fruits)
left, right, current = 0, length - 1, {}
currentLength, longestLength = 0, 0
for right in range(0, length):
current[fruits[right]] = current.get(fruits[right], 0) + 1
while len(current) > 2:
current[fruits[left]] -= 1
if current[fruits[left]] == 0:
del current[fruits[left]]
left += 1
currentLength = right - left + 1
longestLength = max(longestLength, currentLength)
return longestLength
```

## Frequently Asked Questions

### What is the sliding window algorithm?

The main idea behind the sliding window technique is to convert two nested loops into a single loop. Usually, the technique helps us to reduce the time complexity from O(n²) or O(n³) to O(n).