Sliding Window
https://github.com/liyin2015/Algorithms-and-Coding-Interviews/blob/master/two_pointer.pdf
Use sliding window technique and store all characters in a int[256] map. Outer while loop use to expand window, inner while loop to shrink window. Update every time.
public int lengthOfLongestSubstring(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
int res = 0;
int[] map = new int[256];
int L = 0, R = 0;
while (R < s.length()) {
map[s.charAt(R)]++;
while (map[s.charAt(R)] > 1) {
map[s.charAt(L)]--;
L++;
}
res = Math.max(res, R - L + 1);
R++;
}
return res;
}159. Longest Substring with At Most Two Distinct Characters
Use a unique count variable to count how many unique characters are in the window. if map[s.charAt(R)] == 1, increase the count, when map[s.charAt(L)] == 0, decrease the count.
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
int res = 0;
int[] map = new int[256];
int L = 0, R = 0, count = 0;
while (R < s.length()) {
map[s.charAt(R)]++;
if (map[s.charAt(R)] == 1) {
count++;
}
while (count > 2) {
map[s.charAt(L)]--;
if (map[s.charAt(L)] == 0) count--;
L++;
}
res = Math.max(res, R - L + 1);
R++;
}
return res;
}340. Longest Substring with At Most K Distinct Characters
Change 2 above to k.
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.isEmpty()) {
return 0;
}
int res = 0;
int[] map = new int[256];
int L = 0, R = 0, count = 0;
while (R < s.length()) {
map[s.charAt(R)]++;
if (map[s.charAt(R)] == 1) {
count++;
}
while (count > k) {
map[s.charAt(L)]--;
if (map[s.charAt(L)] == 0) count--;
L++;
}
res = Math.max(res, R - L + 1);
R++;
}
return res;
}
public int totalFruit(int[] tree) {
int n = tree.length;
int[] map = new int[n];
int res = 0, count = 0;
for (int L = 0, R = 0; R < n; R++) {
int rc = tree[R];
if (++map[rc] == 1) {
count++;
}
while (count > 2) {
int lc = tree[L++];
if (--map[lc] == 0) {
count--;
}
}
res = Math.max(res, R - L + 1);
}
return res;
}Use sliding window to keep track of the records. HashMap to record char and its count. Preprocess target string with map. Use char count == 0 and length count == t.length() to represent when all records are found
String: ADOBECODEBANC
j i
If (map.contains(nums[i]) reduce count of that char, when count >=0 , foundCount++;
While foundCount == t.length(). Update result. And reduce window size by moving j.
When map.contains(nums[j]), count of char ++, when map.get(char[j]) > 1, foundCount--; and j++;
public String minWindow(String s, String t) {
int[] map = new int[256];
for (char c : t.toCharArray()) {
map[c]++;
}
int min = Integer.MAX_VALUE, minLeft = 0;
int L = 0, R = 0, count = 0;
while (R < s.length()) {
if (map[s.charAt(R)]-- > 0) {
count++;
}
while (count == t.length()) {
if (R - L + 1 < min) {
min = R - L + 1;
minLeft = L;
}
if (map[s.charAt(L)]++ >= 0) {
count--;
}
L++;
}
R++;
}
return min == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + min);
}438. Find All Anagrams in a String
先做一个Map来存P里面的character数，用一个count来存找到了多少个char
右边一直走，把碰到的c在map里减少一个，每减少一个 (map[R]-- > 0) 说明找到一个p中的字符，count++
在R - L + 1 == p.length()的情况下，说明找到了一个和P长度一样的Window，这时候看count也等于p.length()的话，说明是一个解
左边if (map[L]++ >= 0) count--; left++;
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int[] map = new int[256];
for (int c : p.toCharArray()) {
map[c]++;
}
int L = 0, R = 0, count = 0;
while (R < s.length()) {
if (map[s.charAt(R)]-- > 0) {
count++;
}
while (R - L + 1 == p.length()) {
if (count == p.length()) {
result.add(L);
}
if (map[s.charAt(L)]++ >= 0) {
count--;
}
L++;
}
R++;
}
return result;
}1456. Maximum Number of Vowels in a Substring of Given Length
int maxVowels(string s, int k) {
std::string vowels = "aeiou";
int vCount = 0, res = 0;
int left = 0;
for (int right = 0; right < s.size(); ++right) {
char c = s.at(right);
if (vowels.find(c) != std::string::npos) {
vCount++;
}
if (right - left >= k) {
char lc = s.at(left);
if (vowels.find(lc) != std::string::npos) {
--vCount;
}
left++;
}
res = max(res, vCount);
}
return res;
}395. Longest Substring with At Least K Repeating Characters
求最长的，每个Char重复至少K次的substring。这个就不能按照普通的SlidingWindow来做，因为不仅要统计每个char重复的次数，而且要看有几个char达到了要求。而且要求是一直在变的。从1到26个char都有可能。
N从1到26循环，每次都要找一下有几个字符，并且字符个数 >= k而且字符的个数和 >= k字符个数相等。在这种情况下更新长度
public int longestSubstring(String s, int k) {
int max = 0;
for (int i = 1; i <= 26; i++) {
max = Math.max(max, helper(s, k, i));
}
return max;
}
private int helper(String s, int k, int uniqueLimit) {
int[] map = new int[256];
int count = 0;
int numNoLessThanK = 0;
int max = 0;
for (int i = 0, left = 0; i < s.length(); i++) {
if (map[s.charAt(i)]++ == 0) count++;
if (map[s.charAt(i)] == k) numNoLessThanK++;
while (count > uniqueLimit) {
if (map[s.charAt(left)]-- == k) numNoLessThanK--;
if (map[s.charAt(left)] == 0) count--;
left++;
}
if (count == uniqueLimit && count == numNoLessThanK) {
max = Math.max(max, i - left + 1);
}
}
return max;
}Use sliding winder to get the count of K different elements. Minus the result by K - 1 different elements. That is exactly K different elements.
public int subarraysWithKDistinct(int[] A, int K) {
return helper(A, K) - helper(A, K - 1);
}
private int helper(int[] A, int K) {
int n = A.length;
int[] map = new int[n + 1];
int count = 0, res = 0;
for (int i = 0, left = 0; i < n; i++) {
if (++map[A[i]] == 1) {
count++;
}
while (count > K) {
if (--map[A[left++]] == 0) {
count--;
}
}
res += i - left + 1;
}
return res;
}713. Subarray Product Less Than K
485. Max Consecutive Ones
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int L = 0, R = 0;
long sum = 0;
int res = Integer.MAX_VALUE;
while (R < nums.length) {
sum += nums[R];
while (sum >= s) {
res = Math.min(res, R - L + 1);
sum -= nums[L++];
}
R++;
}
return res == Integer.MAX_VALUE ? 0 : res;
}
1100. Find K-Length Substrings With No Repeated Characters
This problem is hard to interpret. It means you have to select k cards from begin or end or both. This is actually a two pointer + sliding window problem. LSum represents the sum on left side, then slide to the left, RSum is the sum on the right side. LSum + RSum is one of the result.
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
int lsum = 0, rsum = 0;
for (int i = 0; i < k; i++) {
lsum += cardPoints[i];
}
int res = lsum + rsum;
for (int i = 0; i < k; i++) {
lsum -= cardPoints[k - i - 1];
rsum += cardPoints[n - i - 1];
res = Math.max(res, lsum + rsum);
}
return res;
}30. Substring with Concatenation of All Words
Get all words into a set of string combinations by using backtracking. Slide window and compare substring. First step took very long since backtracking takes O(k^2) where k is size of words
Save target words and their count to a target map.
Use i to control left bound, j as right bound, to slide window. J is the index in words[], which also control length
Create a new map (“seen”) every move, count the words between i and j. If there are unseen words, break. Otherwise put seen words in the “seen” map.
就把该单词存到新的 HashMap 中，并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ，如果大了，就代表该子串不是我们要找的，接着判断下一个子串就可以了。如果不大于，那么我们接着判断下一个单词的情况。子串扫描结束，如果子串的全部单词都符合，那么该子串就是我们找的其中一个。
T：假设 s 的长度是 n，words 里有 m 个单词，那么时间复杂度就是 O（n * m）. S：两个 HashMap，假设 words 里有 m 个单词，就是 O（m）。
如果S的长度小于T说明不可能，Return false
做两个Map，把S， T都count一下。
i来循环T，并且update 这个window的字符。看两个map是不是相等：
int len = s1.length();
for (int i = 0; i + len < s2.length(); i++) {
if (isSame(s1map, s2map)) return true;
s2map[s2.charAt(i + len) - 'a']++;
s2map[s2.charAt(i) - 'a']--;
}
return isSame(s1map, s2map);
Number of Substrings Containing All Three Characters
Count Number of Nice Subarrays
Replace the Substring for Balanced String
Max Consecutive Ones III
Binary Subarrays With Sum
Subarrays with K Different Integers
Fruit Into Baskets
Shortest Subarray with Sum at Least K
Minimum Size Subarray Sum
424. Longest Repeating Character Replacement
function characterReplacement(s: string, k: number): number {
const freq: Record<string, number> = {};
let maxCount = 0; // max frequency of a single char in current window
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
const rightChar = s[right];
freq[rightChar] = (freq[rightChar] || 0) + 1;
maxCount = Math.max(maxCount, freq[rightChar]);
// If more than k chars need to be replaced, shrink window
while ((right - left + 1) - maxCount > k) {
const leftChar = s[left];
freq[leftChar]--;
left++;
// Note: no need to update maxCount here because it only ever grows or stays the same,
// which is fine for correctness in this problem.
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
2962. Count Subarrays Where Max Element Appears at Least K Times
function countSubarrays(nums: number[], k: number): number {
const maxElement = Math.max(...nums);
let left = 0;
let ans = 0;
let maxElementInWindow = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === maxElement) {
maxElementInWindow++;
}
while (maxElementInWindow >= k) {
if (nums[left] === maxElement) {
maxElementInWindow--;
}
left++;
}
ans += left;
}
return ans;
};2067. Number of Equal Count Substrings
class Solution {
public:
int equalCountSubstrings(string s, int count) {
int ans = 0;
int n = s.size();
for (int distinctTarget = 1; distinctTarget <= 26; distinctTarget++) {
vector<int> freq(26, 0);
int left = 0, right = 0;
int unique = 0; // number of unique chars in window
int countAtTarget = 0; // chars whose frequency == count
while (right < n) {
int idx = s[right] - 'a';
freq[idx]++;
if (freq[idx] == 1) unique++;
if (freq[idx] == count) countAtTarget++;
while (unique > distinctTarget || (right - left + 1) > distinctTarget * count) {
int leftIdx = s[left] - 'a';
if (freq[leftIdx] == count) countAtTarget--;
freq[leftIdx]--;
if (freq[leftIdx] == 0) unique--;
left++;
}
if (unique == distinctTarget && countAtTarget == distinctTarget
&& (right - left + 1) == distinctTarget * count) {
ans++;
}
right++;
}
}
return ans;
}
};2831. Find the Longest Equal Subarray
class Solution {
public:
int longestEqualSubarray(vector<int>& nums, int k) {
unordered_map<int, vector<int>> countMap;
int left = 0;
int res = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
countMap[nums[i]].push_back(i);
}
for (const auto& [val, indicies] : countMap) {
int left = 0;
for (int right = 0; right < indicies.size(); ++right) {
// indicies[right] - indicies[left] - (right - left) <> k
while (indicies[right] - indicies[left] - (right - left) > k) {
++left;
}
res = max(res, right - left + 1);
}
}
return res;
}
};Last updated
Was this helpful?