Some time ago, I was busy writing a series of articles, and the progress of brushing algorithmic problems was delayed a lot. I just came across a topic that requires a sliding window, and after doing so, I found it quite interesting and necessary to have a good chat about sliding windows.
The so-called slide window is an abstract concept of optimization algorithms, mainly used for solving subarray or subsequence problems in linear structures such as arrays and strings. The whole idea is to reduce repeated computations by maintaining a window that slides over the array, one unit distance at a time.
Sliding windows are generally divided into 2 types:
Fixed Size Window: The size of the window is fixed, and the problem is solved by moving the window's position on the array or string. For example: find the maximum sum of fixed length subarrays of an array species.
Variable Size Window: Dynamically increase or decrease the window according to the conditions. For example: find the largest subarray that does not exceed a given sum.
For fixed-size window problems, the most typical is leetCode question thirty:
Given a string s and an array words containing multiple words of the same lengthThe requirement is to find the number in sAll starting indexesThe substrings corresponding to these starting indexes are exactly the same as all the words in words.tandem arrangement（No limitation on the order(but each word must be used once).
Example:
Input:
s = "barfoothefoobarman"
words = ["foo", "bar"]
Output:
[0, 9]
Explanation:
The substring from index 0 is "barfoo", which is a concatenation of ["foo", "bar"].
The substring from index 9 is "foobar", which is also a concatenation of ["foo", "bar"].
Using a sliding window, the following code can be easily implemented:
from collections import Counter
from typing import List
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
word_len = len(words[0])
word_count = len(words)
total_len = word_len * word_count
word_freq = Counter(words)
result = []
# (math.) ergodic word_len substandard
for i in range(word_len):
left = i
right = i
seen = Counter()
matched_count = 0
while right + word_len <= len(s):
# Extract the current word
word = s[right:right + word_len]
right += word_len
if word in word_freq:
seen[word] += 1
matched_count += 1
# 如果当前单词出现substandard数超过了预期，Move left pointer
while seen[word] > word_freq[word]:
left_word = s[left:left + word_len]
seen[left_word] -= 1
matched_count -= 1
left += word_len
# If the number of words matched is equal to words Number of words in，Record Starting Index
if matched_count == word_count:
(left)
else:
# The current word is not words center，Reset Window
()
matched_count = 0
left = right
return result
In the above code, two pointers, left and right, are defined that constantly move the positions of left and right to make the strings in the window match the conditions. When a word occurs more frequently than expected, the left variable is moved to the right by one word length (word_len) and the number of corresponding words in the seen variable is reduced, along with matched_count.
When a word is encountered that is not in the provision, the entire window is reset.
Here the first loop is more tricky and iterates through all the non-repeating results by only looping through the word length (word_len).
The second example is the variable size window case, titled:
Finds the maximum length subarray of an array whose sum does not exceed k.
def get_max_sub_arry_length(nums: List[int], k: int) -> int:
left = 0
max_length = 0
sum = 0
for right in range(len(nums)):
# Expanded window
sum += nums[right]
while sum > k and left <= right:
# Zoom in
sum -= nums[left]
left += 1
# Recalculate maximum length
max_length = max(max_length, right - left + 1)
return max_length
nums = [1,2,3,4,5]
k = 8
print(get_max_sub_arry_length(nums, k))