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

def lengthOfLongestSubstring(self, s: str) -> int:
    dic = {}
    L = 0
    res = 0
    for R in range(len(s)):
        if s[R] not in dic:
            dic[s[R]] = 0
        dic[s[R]] += 1
        while dic[s[R]] > 1:
            lc = s[L]
            dic[lc] -= 1
            L += 1
        res = max(res, R - L + 1)
    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;
}

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

def totalFruit(self, tree: List[int]) -> int:
    dic = {}
    L, R, n, count, res = 0, 0, len(tree), 0, 0;
    while R < n:
        rc = tree[R]
        if rc not in dic:
            dic[rc] = 0;
        dic[rc] += 1
        if dic[rc] == 1:
            count += 1
        while count > 2:
            lc = tree[L]
            dic[lc] -= 1
            if dic[lc] == 0:
                count -= 1
            L += 1
        res = max(res, R - L + 1)
        R += 1
    return res

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

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