The pattern of question can be solved by Two Pointers algorithms is

Return the length of the longest contiguous subarray [u,v] of array A that [u,v] meets the requirement X. With X is a requirement such that: if [u,v] doesn't meet X, then [u,v'] doesn't meet X too (v' > v).

Example:

- Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s. - Given a string s, find the length of the longest substring t that contains at most 2 distinct characters.
- Given a string, find the length of the longest substring without repeating characters.

The naive algorithm is considering all subarray [u,v] (0 <= u <= v < n) and check if [u,v] meet X. The complexity is O(n^2).

```
int u = 0, v = 0;
for(u = 0; u < n; u++)
for(v = u; v < n; v++)
if (ok(fx(u,v), X) res = max(res, v - u + 1);
```

However, X has a property that if [u,v] doesn't meet requirement X then [u,v'] will not meet X with **v' > v**. Take advantage of this property:

- we can stop v as soon as [u,v] no longer meet requirement X

```
int u = 0, v = 0;
for(int u = 0; u < n; u++)
for(int v = u; v < n; v++)
if (ok(fx(u,v), X) res = max(res, v - u + 1);
else break;
```

- after we stop v (by
*break*), [u, v-1] is the last valid subarray we consider (lenght = v-u), we no need to consider all the subarrays [u, k], where k < v, because k - u + 1 < v - u + 1 anyway, i.e. we cannot get a better outcome when considering [u,k] (k < v).

**Step 1**: Initially i = j = 0

**Step 2**: Try to extend i as far as possible such that subarray [j,i] fullfils the requirement X.

**Step 3**: When i reaches the point where subarray [j,i] doesn't meet requirement X, we stop and increase j until [j,i] meet requirement X again. Then we repeat Step 2. Until i reach size of the array.

The common code for all of this type of questions:

- a is the array we concern
- fx(u,v) is the function of subarray [u,v] we consider against condition X.

```
int n = a.size();
int i = 0, j = 0;
// calculate fx(0,0)
while (i < n) {
// if meet the requirement X
if (ok(fx(j, i), X)) {
res = max(res, i - j + 1);
i++;
if (i < n) {
// calculate fx(j,i);
}
} else {
j++;
// calculate fx(j,i);
}
}
```

I prefer calling this technique **Snake technique** because the subarray [i,j] is moving like a snake during the algorithm.

Note that only when requirement X has the above mentioned property, we can apply this technique. For example, we cannot use this technique for the following problem:

Given a binary array, find the longest contiguous subarray that has number of 1 strictly greater than number of 0. (https://leetcode.com/problems/longest-well-performing-interval/)

0 1 2 3 4 5 6 7

**0 1 0** 0 1 1 1 1

We can easily see in this example, subarray [0,2] (0, 1, 0) does not meet requirement X but [0,7] (0, 1, 0, 0, 1, 1, 1, 1) still meet requirement X.

##### Example 1: Given an array A of 0s and 1s, we may change up to K values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s.

This question is equivalent to Find the longest contiguous subarray that has at most K 0. In this case:

- Condition X is "
**has at most K 0**" - fx(u,v) will be number of 0 in subarray [u,v]
- ok(fx(u,v), X) will be
**fx(u,v) <= K**

We have the following code:

```
int longestOnes(vector<int>& a, int K) {
int n = a.size();
int i = 0, j = 0, res = 0;
int num = a[i] == 0 ? 1 : 0;
while (i < n) {
if (num <= K) {
res = max(res, i - j + 1);
i++;
if (i < n) num += (a[i] == 0);
} else {
num -= (a[j] == 0);
j++;
}
}
return res;
}
```

##### Example 2: Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

- Condition X is "contains at most 2 distinct characters"
- fx(u,v) is calculated a bit more complicated: we need to maintain a
*set A*of distinct character of subarray [u,v], and to update*A*, we use a*map count*to count frequency of each character in*A* - ok(fx(u,v), X) will be
**A.size() <= 2**

```
int lengthOfLongestSubstringTwoDistinct(string s) {
unordered_set<char> a;
unordered_map<char, int> count;
int n = s.size();
if (n == 0) return 0;
int i = 0, j = 0, res = 0;
a.insert(s[0]);
count[s[0]] = 1;
while (i < n) {
if (a.size() <= 2) {
res = max(res, i - j + 1);
i++;
if (i < n) {
a.insert(s[i]);
count[s[i]]++;
}
} else {
count[s[j]]--;
// only remove s[j] from a if count[s[j]] == 0
if (count[s[j]] == 0) a.erase(s[j]);
j++;
}
}
return res;
}
```

The key here is to determine X, fx(u,v) and the way to calculate fx(u,v).

Some problems can be solved by this Snake technique:

- https://leetcode.com/problems/max-consecutive-ones-ii/
- https://leetcode.com/problems/max-consecutive-ones-iii/
- https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
- https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
- https://leetcode.com/problems/longest-substring-without-repeating-characters/
- https://leetcode.com/problems/subarray-product-less-than-k/
- https://leetcode.com/problems/fruit-into-baskets/