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
`right`

increases, in the optimal solution, the`left`

index 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`

.