Sliding Window

Problems

#	Problem	Difficulty	Hint	Tags
20	Best Time to Buy and Sell Stock - LeetCode	Easy	Hint Let the left pointer be the buy value and the right pointer be the sell value. Move the pointers accordingly.	#array #dynamicprogramming
3	Longest Substring Without Repeating Characters - LeetCode	Medium	Hint Template sliding window problem. Update the pointers based on characters in the set.	#string #hashtable #slidingwindow
424	Longest Repeating Character Replacement - LeetCode	Medium	Hint Keep a count of the characters in the window. It is always optimal to try and replace the most frequent character in the string. When the number of replacements exceeds k. How do we calculate this?	#array #hashtable #slidingwindow
76	Minimum Window Substring - LeetCode	Hard	Hint Keep character count of t and the current substring. Move the window when we encounter a valid substring that contains all the chars from t.	#hashtable #slidingwindow #string
239	Sliding Window Maximum - LeetCode	Hard	Hint A heap can be used to efficiently get the max element in O(1) time. Pop elements from the heap until the top element is in the current window.	#array #queue #slidingwindow #heap #monotonicqueue

Sliding window involves two pointers that never overtake each other. It is best used when encountering a problem that involves contiguous subarrays or substrings. It keeps a "range" of data that steps through the problem, updating the left and right pointers accordingly.

maxLength = 0
l = 0
seen = set()
  
for r in range(len(s)):
	while s[r] in seen:
		seen.remove(s[l])
		l += 1
	seen.add(s[r])
	maxLength = max(maxLength, r - l + 1)

return maxLength

The above is a template for a sliding window problem (Longest Substring Without Repeating Characters) with the index of the for loop serving as the right pointer and a left pointer starting at 0 that gets updated in a while loop.