3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.

substring要想到滑动窗口，不过这道题是求最大的窗口而已，每步都要更新max
tricky的地方在于start只能向右移动，比如abba碰见最后的a，start会移动index=1的地方，就错了。

    public int lengthOfLongestSubstring(String s) {
        // key is char value its index
        Map<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                // find duplicate, update start
                // start can only move to right
                if (start < map.get(s.charAt(i)) + 1) {
                    start = map.get(s.charAt(i)) + 1;  
                }
            }
            max = Math.max(max, i - start + 1);
            map.put(s.charAt(i), i);
            
        }
        return max;
        
    }

先找到满足条件的，记录，尝试缩小窗口
while循环三步走，先update最值，删开头尝试新可能性，最后挪start

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

1+3+1+3=8>7，所以让8减第一个元素尝试去缩小window，更新最小值，然后减第二个直到不能缩小，指针停下。
while循环三步走，先update最值，删开头尝试新可能性，最后挪start

    public int minSubArrayLen(int s, int[] nums) {
        int sum = 0, start = 0, res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= s) {
                res = Math.min(res, (i - start + 1));
                sum -= nums[start];
                start++;
            }
        }
        return (res == Integer.MAX_VALUE) ? 0 : res;
    }

76. Minimum Window Substring

S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

思路和上题一样，找最小的窗口
Sliding Window

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int start = 0, minSize = Integer.MAX_VALUE, minStart = 0, count = 0;
        for (int i = 0; i < s.length(); i++) {
            
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                
                map.put(c, map.get(c) - 1);
                if (map.get(c) >= 0) {
                    count++;
                }
            }
            // A -1, B 0， 存在负数的可能
            while (count == t.length()) {
                // update
                if (i - start + 1 < minSize) {
                    minSize = i - start + 1;
                    minStart = start;
                }
                // delete first
                char r = s.charAt(start);
                if (map.containsKey(r)) {
                    map.put(r, map.get(r) + 1);
                    // 注意是 > 0, 过剩了再减 ex. AAB
                    if (map.get(r) > 0) {
                        count--;
                    }
                }
                start++;
            }

        }
        return (minSize == Integer.MAX_VALUE) ? "" : s.substring(minStart, minStart + minSize);
    }
}

438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

一开始对anagram的定义有些误解。要明白start指针移动的过程。套路和上题一样

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int start = 0;
        int count = 0;
        for (int end = 0; end < s.length(); end++) {
            char cur = s.charAt(end);
            if (map.containsKey(cur)) {
                map.put(cur, map.get(cur) - 1);
                if (map.get(cur) >= 0) {
                    count++;
                }
            }
            while (count == p.length()) {
                char c = s.charAt(start);
                if(map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                    if (map.get(c) > 0) {
                        count--;
                    }
                }
                if (end - start + 1 == p.length()) {
                    res.add(start);
                }
                start++;
            }
        }
        return res;
    }