LeetCode 76. Minimum Window Substring

Problem

LeetCode 76. Minimum Window Substring

1. 题目简述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

Note:

1 <= s.length, t.length <= 105

s 和 t 由英文字母组成

2. 算法思路

相关问题：

1. 力扣30题

所有的思路都在code的注释里了，参考30题。

滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        // 初始化目标词典表
        String res = "";
        int n = t.length();
        Map<Character, Integer> total = new HashMap();
        for (int i = 0; i < n; i++) {
            total.put(t.charAt(i), total.getOrDefault(t.charAt(i), 0) + 1);
        }
        
        // 和30题的思路是一致的，滑动窗口，每次向右滑动一位，判断当前window里的所有字符是否满足要求，关于这个满足要求，可以用一个count值来表示，每次移动的时候做判断。
        // 那么什么时候移动start，什么时候移动end呢？先移动end，直到start到end满足要求后，start向后移动，如果移动一位发现当前的start到end又不满足要求了，则再次移动end，直至终结。
        // 这里能用双指针是因为单调性！！！
        int start = 0, end = 0, count = 0;
        Map<Character, Integer> window = new HashMap();
        char[] arr = s.toCharArray();
        
        for (int i = 0, j = 0; j < s.length(); j++) {
            // 关于为什么这里for循环只去考虑j呢？也就是比较靠后的指针，因为每次更新j的时候，i都会向后移动尽可能多的位数，如果移动i以后发现满足要求（比当前更小），那就更新。
            window.put(arr[j], window.getOrDefault(arr[j], 0) + 1);
            if (window.get(arr[j]) <= total.getOrDefault(arr[j], 0)) {
                count++;
            }
            
            // 如果count == t.length()并且window里面的第i个字符是多余的，那就一直将i右移。
            while (count == n && window.getOrDefault(arr[i], 0) > total.getOrDefault(arr[i], 0)) {
                window.put(arr[i], window.get(arr[i]) - 1);
                i++;
            }
            
            // 此时的i到j，如果依然是count == n，说明是符合要求的一种可能性，判断是否需要更新。这里是j - i + 1，不是j - i，因为i到j是双闭区间，不是左闭右开区间。
            if (count == n && (j - i + 1 < res.length() || res.equals(""))) {
                res = s.substring(i, j + 1);
            }
        }
        
        return res;
    }
}