最小覆盖子串「变题」

76. 最小覆盖子串

开头先来一个小插曲，关于「滑动窗口」相关的总结可见 滑动窗口

注意：Integer 的比较最好使用equals()，否则值大了后会比较失败

xxxxxxxxxx
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> win = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int n = s.length(), valid = 0, ans = n + 1, mi = 0;
    int l = 0, r = 0;
    while (r < n) {
        char c = s.charAt(r++);
        if (need.containsKey(c)) {
            win.put(c, win.getOrDefault(c, 0) + 1);
            // 注意 Integer 的比较
            if (win.get(c).equals(need.get(c))) valid++;
        }
        while (valid >= need.size()) {
            if (r - l < ans) {
                ans = r - l;
                mi = l;
            }
            char d = s.charAt(l++);
            if (need.containsKey(d)) {
                if (win.get(d).equals(need.get(d))) valid--;
                win.put(d, win.get(d) - 1);
            }
        }
    }
    return ans == n + 1 ? "" : s.substring(mi, mi + ans);
}

变题一：数组版

题目详情可见 面试题 17.18. 最短超串

xxxxxxxxxx
public int[] shortestSeq(int[] big, int[] small) {
    Map<Integer, Integer> need = new HashMap<>();
    Map<Integer, Integer> win = new HashMap<>();
    for (int x : small) {
        need.put(x, need.getOrDefault(x, 0) + 1);
    }
    int n = big.length, valid = 0, cnt = n + 1, mi = 0;
    int l = 0, r = 0;
    while (r < n) {
        int c = big[r++];
        if (need.containsKey(c)) {
            win.put(c, win.getOrDefault(c, 0) + 1);
            // 注意 Integer 的比较
            if (win.get(c).equals(need.get(c))) valid++;
        }
        while (valid >= need.size()) {
            if (r - l < cnt) {
                cnt = r - l;
                mi = l;
            }
            int d = big[l++];
            if (need.containsKey(d)) {
                if (win.get(d).equals(need.get(d))) valid--;
                win.put(d, win.get(d) - 1);
            }
        }
    }
    if (cnt == n + 1) return new int[]{};
    return new int[]{mi, mi + cnt - 1};
}

变题二：必须和子串相等

题目详情可见 30. 串联所有单词的子串

xxxxxxxxxx
public List<Integer> findSubstring(String s, String[] words) {
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.put(w, need.getOrDefault(w, 0) + 1);
    List<Integer> ans = new ArrayList<>();
    int n = s.length(), m = words[0].length(), len = m * words.length;
    for (int i = 0; i < m; i++) {
        Map<String, Integer> win = new HashMap<>();
        int l = i, r = i, valid = 0;
        while (r + m <= n) {
            String cur = s.substring(r, r + m);
            if (need.containsKey(cur)) {
                win.put(cur, win.getOrDefault(cur, 0) + 1);
                if (win.get(cur).equals(need.get(cur))) valid++;
            }
            while (valid >= need.size()) {
                if (r + m - l == len) {
                    ans.add(l);
                }
                String d = s.substring(l, l + m);
                if (need.containsKey(d)) {
                    if (win.get(d).equals(need.get(d))) valid--;
                    win.put(d, win.get(d) - 1);
                }
                l = l + m;
            }
            r = r + m;
        }
    }
    return ans;
}