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/