# Sliding Window Concepts

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:

1. We keep a window `(left, right]`;
2. 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`.