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);
count[s] = 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: