3. Sliding Window

Sliding window

Template

public int slidingWindow(String s) {
    // ========= 模板：定义相关数据结构，初始化工作============
    HashMap<Character, Integer> windowMap = new HashMap<>();
  
    int left, right, res;
    left = right = res = 0;

    // ================== 模板：开始滑动窗口=====================
    while (right < s.length()) {

        // =========== 模板：向右滑动窗口，装填满足的字符到map中==========
        char c = s.charAt(right);
        right++;
        windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

        // =========== 根据题意：此时“有可能”出现满足条件的解 ==========
        // 判断左侧窗口是否要收缩
        while (window_map.get(c) > 1) {
            char d = s.charAt(left);
            left++;
            // 进行窗口内数据的一系列更新
            windowMap.put(d, windowMap.getOrDefault(d, 0) - 1);
        }
        // 在这里更新答案
        res = Math.max(res, right - left);
    }
    return res;
}

Typic problems

• Find longest no repeated substring

//Find the length of longest no repeat substring from a given string
public int lengthOfLongestNoRepeatSubstring(String s) {
    Map<Character, Integer> charMap = new HashMap<>();
    int left = 0, right = 0, result = 0;
    while (right < s.length()) {
        //Expand the window
        char ch = s.charAt(right);
        charMap.put(ch, charMap.getOrDefault(ch, 0) + 1);
        right++;

        //shrink the window
        while (charMap.get(ch) > 1) {
            char leftChar = s.charAt(left);
            charMap.put(leftChar, charMap.getOrDefault(leftChar, 0) - 1);
            left++;
        }

        //Save the results
        result = Math.max(result, right - left);
    }
    return result;
}

• Minimum coverage window substring

//Find the minimun substring of s1 that can cover all chars in s2
public String minCoverageWindowSubstring(String s1, String s2) {
    // 记录t 以及 滑动窗口window中 字符与个数的映射关系
    HashMap<Character, Integer> windowMap = new HashMap<>();
    HashMap<Character, Integer> needMap = new HashMap<>();
    for (int i = 0; i < s2.length(); i++) {
        char c1 = s2.charAt(i);
        needMap.put(c1, needMap.getOrDefault(c1, 0) + 1);
    }
    // 双指针, 
    int left = 0, right = 0, valid = 0;
    // 用于更新满足的窗口window的长度,如果是len一直是MAX_VALUE，说明没有满足的串
    int len = Integer.MAX_VALUE;
    // 用于记录window串的起始位置，则返回 s[start, len]
    int start = 0;

    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        // 只要c是t中出现的字符就更新
        if (needMap.containsKey(c)) {
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
            // 更新c字符出现的次数，重复字符只会算一个valid，这个跟上面array算法中的区别
            if (windowMap.get(c).equals(needMap.get(c))) {
                valid++;
            }
        }
        // ----------------------------------
        // 收缩window的长度
        while (valid == needMap.size()) {
            // 更新并记录window的长度,以及window的起始位置start
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            //d 是将移出窗口的字符
            char d = s.charAt(left);
            left++;

            if (needMap.containsKey(d)) {
                if (windowMap.get(d).equals(needMap.get(d))) {
                    valid--;
                }
                windowMap.put(d, windowMap.get(d) - 1);
            }
        }
    } 
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

• Find all Anagrams from a string of another string

public List<Integer> findAnagrams(String s, String p) {
    // ========= 模板：定义相关数据结构，初始化工作============
    HashMap<Character, Integer> windowMap = new HashMap<>();
    HashMap<Character, Integer> needMap = new HashMap<>();
    for (int i = 0; i < p.length(); i++){
        char c1 = p.charAt(i);
        needMap.put(c1, needMap.getOrDefault(c1, 0) + 1);
    }
    int left = 0, right = 0, count = 0;
    
    ArrayList<Integer> res = new ArrayList<>();

    // ================== 模板：开始滑动窗口=====================
    while (right < s.length()) {

        // =========== 模板：向右滑动窗口，装填满足的字符到map中==========
        char c = s.charAt(right);
        right++;
        if (p_map.containsKey(c)) {
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
            if (windowMap.get(c).equals(needMap.get(c))) {
                count++;
            }
        }

        // =========== 根据题意：此时“有可能”出现满足条件的解 ==========
        // Notice the time of potention results and shrink window
        while (right - left == p.length()) {

            // ============= 根据题意：获取“真正”满足条件的解 =============
            if (count == needMap.size()){
                res.add(left);
            }

            // ========== 模板：左指针向右滑动，寻找下一个可行解/优化已知解======
            char d = s.charAt(left);
            left++;
            if (needMap.containsKey(d)) {
                if (windowMap.get(d).equals(needMap.get(d))) {
                    count--;
                }
                windowMap.put(d, windowMap.getOrDefault(d, 0) - 1);
            }
        }
    }
    return res;
}