Sliding Window

https://github.com/liyin2015/Algorithms-and-Coding-Interviews/blob/master/two_pointer.pdf

• https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

• https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/

• https://leetcode.com/problems/replace-the-substring-for-balanced-string/

• https://leetcode.com/problems/max-consecutive-ones-iii/

• https://leetcode.com/problems/subarrays-with-k-different-integers/

• https://leetcode.com/problems/fruit-into-baskets/

• https://leetcode.com/problems/get-equal-substrings-within-budget/

• https://leetcode.com/problems/longest-repeating-character-replacement/

• https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

• https://leetcode.com/problems/minimum-size-subarray-sum/

• https://leetcode.com/problems/sliding-window-maximum/

3. Longest Substring Without Repeating Characters

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.

Java

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;
}

Python

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;
}

904. Fruit Into Baskets

Java

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;
}

Python

76. Minimum Window Substring

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;
    }

992. Subarrays with K Different Integers

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

209. Minimum Size Subarray Sum

    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

1423. Maximum Points You Can Obtain from Cards

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.

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/discuss/597825/Simple-Clean-Intuitive-Explanation-with-Visualization

    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

1. 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

2. Slide window.

   1. Save target words and their count to a target map.

   2. Use i to control left bound, j as right bound, to slide window. J is the index in words[], which also control length

   3. 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.

   4. 就把该单词存到新的 HashMap 中，并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ，如果大了，就代表该子串不是我们要找的，接着判断下一个子串就可以了。如果不大于，那么我们接着判断下一个单词的情况。子串扫描结束，如果子串的全部单词都符合，那么该子串就是我们找的其中一个。

   5. T：假设 s 的长度是 n，words 里有 m 个单词，那么时间复杂度就是 O（n * m）. S：两个 HashMap，假设 words 里有 m 个单词，就是 O（m）。

3. Optimized Slide window

567. Permutation in String

如果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;
    }
};