滑动窗口 + 字符串（最小覆盖子串 · 字符串的排列）

最小覆盖子串（LeetCode 76）

在 s 中找包含 t 所有字符的最小子串。

模板：滑动窗口

String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

    int l = 0, r = 0, valid = 0;
    int start = 0, minLen = Integer.MAX_VALUE;

    while (r < s.length()) {
        char c = s.charAt(r++);
        // 扩大窗口
        if (need.containsKey(c)) {
            window.merge(c, 1, Integer::sum);
            if (window.get(c).equals(need.get(c))) valid++;  // 满足一个字符需求
        }
        // 尝试收缩窗口
        while (valid == need.size()) {
            if (r - l < minLen) { minLen = r - l; start = l; }
            char d = s.charAt(l++);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.merge(d, -1, Integer::sum);
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

字符串的排列 / 找所有字母异位词（LeetCode 567 / 438）

固定窗口大小 = t.length()，窗口滑动：

// 567: 返回 s2 是否包含 s1 的排列
boolean checkInclusion(String s1, String s2) {
    int[] need = new int[26], window = new int[26];
    for (char c : s1.toCharArray()) need[c - 'a']++;
    int k = s1.length();

    for (int i = 0; i < s2.length(); i++) {
        window[s2.charAt(i) - 'a']++;
        if (i >= k) window[s2.charAt(i - k) - 'a']--;  // 移出左端
        if (Arrays.equals(need, window)) return true;
    }
    return false;
}

// 438: 返回所有起始索引
List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    int[] need = new int[26], window = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
    int k = p.length();
    for (int i = 0; i < s.length(); i++) {
        window[s.charAt(i) - 'a']++;
        if (i >= k) window[s.charAt(i - k) - 'a']--;
        if (Arrays.equals(need, window)) res.add(i - k + 1);
    }
    return res;
}

无重复字符的最长子串（LeetCode 3）

动态窗口：

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int l = 0, maxLen = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (map.containsKey(c)) l = Math.max(l, map.get(c) + 1);  // 跳到重复位置之后
        map.put(c, r);
        maxLen = Math.max(maxLen, r - l + 1);
    }
    return maxLen;
}

至多含 K 个不同字符的最长子串（LeetCode 340）

int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> freq = new HashMap<>();
    int l = 0, maxLen = 0;
    for (int r = 0; r < s.length(); r++) {
        freq.merge(s.charAt(r), 1, Integer::sum);
        while (freq.size() > k) {
            char left = s.charAt(l++);
            freq.merge(left, -1, Integer::sum);
            if (freq.get(left) == 0) freq.remove(left);
        }
        maxLen = Math.max(maxLen, r - l + 1);
    }
    return maxLen;
}

滑动窗口通用框架总结

right 向右扩展直到满足条件
└─ 满足：
   ├─ 记录答案（窗口缩到最小时）
   └─ left 向右收缩
left 向右收缩直到不满足条件
└─ 继续扩展 right