Templates

def slidingWindow(s: str):
    window = ...

    left, right = 0, 0
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        window.add(c)
        # 增大窗口
        right += 1
        # 进行窗口内数据的一系列更新
        ...

        # print(f"window: [{left}, {right})")

        # 判断左侧窗口是否要收缩
        while left < right and window needs shrink:
            # d 是将移出窗口的字符
            d = s[left]
            window.remove(d)
            # 缩小窗口
            left += 1
            # 进行窗口内数据的一系列更新
            ...

Question types

Fixed size sliding window

• Find the size of the window required, say K.
• Compute the result for 1st window, i.e. include the first K elements of the data structure.
• Then use a loop to slide the window by 1 and keep computing the result window by window.

Variable size sliding window

• In this type of sliding window problem, we increase our right pointer one by one till our condition is true.
• At any step if our condition does not match, we shrink the size of our window by increasing left pointer.
• Again, when our condition satisfies, we start increasing the right pointer and follow step 1.
• We follow these steps until we reach to the end of the array.

	l = 0
	cache = {}
	maxLen = 0
	
	for r in range(length):
		while s[r] is True:
			cache.remove(s[l])
			l += 1

		cache.add(s[r])
		maxLen = max(maxLen, r - l + 1)

	return maxLen

Double Ended Queue

• Record the index of the element in the queue
• When the index exceeds k, pop from the front
• Also need to ensure the queue is in a decreasing order

239. Sliding Window Maximum

Remove duplicates with fast slow pointer

• When condition satisfies (Such as there is no duplicate), swap the element at fast pointer to slow pointer position
• When the condition fail (Such as there exist a duplicate), only move the fast pointer forward

80. Remove Duplicates from Sorted Array II