The Sliding Window technique is usually used to find the shortest or longest qualified subarray. For example, find the shortest subarray whose sum is no less than K.
A Naive Idea
The problem is straightforward if, for every right index, we could find the rightmost left index so that the window has sum >= K. This can be done by another loop. The overall complexity will be O(n^2)
Sliding Window
We could use the Sliding Window technique to improve the time complexity to O(n), if the problem has the following monotonic property:
- We keep a window
(left, right]; - As the index
rightincreases, in the optimal solution, theleftindex won’t decrease.
Given the above property, it is not hard to see that the left index and the right index will only traverse the whole array once, which is of complexity O(n).
Shortest Subarray With Sum At Least K
If the window(left, right] qualifies, as right increases, left won’t decrease, since (x, right+1], x<left must be longer than (left, right]. This property holds no matter numbers in the array are positive or negative.
Longest Subarray With At Most K 0s
If the window (left, right] qualifies, as right increases, left won’t decrease, since (left, right] is already the longest qualified subarray for all (x, right], introducing right+1 won’t decrease the number of 0s, so the index left can’t move left.
Think in another way: if (left, right] contains more than K 0s, (x, y] x<left, y>right can’t be qualified.
Longest Substring With At Most K Unique Characters
If the window (left, right] qualifies, as right increases, left won’t decrease, since (left, right] is already the longest qualified subarray for all (x, right], introducing right+1 won’t decrease the number of distinct characters, so the index left can’t move left.
Longest Substring With No Duplicate Characters
If the window (left, right] qualifies, as right increases, left won’t decrease, since (left, right] is already the longest qualified subarray for all (x, right], introducing right+1 won’t decrease the number of distinct characters, so the index left can’t move left.
Longest Substring With At Least K Same Characters
This problem is tricky. At first glance, the monotonic property doesn’t hold: If the window (left, right] qualifies, as right increases, left might decrease, since right+1 introduces a new char, which might make some unqualified windows (x, right], x<left qualified.
However, if we introduce another constraint: find the longest substring with at least K same characters and L unique characters, the monotonic property holds:
If the window (left, right] qualifies, as right increases, left won’t decrease, since (left, right] is already the longest qualified subarray for all (x, right], introducing right+1 won’t decrease the number of distinct characters, so the index left can’t move left.
And we traverse L from 1 to 26.