76. Minimum Window Substring

• 变量定义：
  • 哈希表counter_s和counter_t表示数组source和target中有效字符的出现次数，其中，我们将有效字符定义为target中出现的字符。
  • start是最小覆盖子串的起始索引，minlen是最小覆盖子串的长度（从0计）。
  • valid表示source的窗口中满足counter_t出现次数要求的字符的个数。注意，相同的字符只计算一次。
  • left和right分别指向滑窗两端。
• 算法流程：
  1. 初始化：left指针和right指针都指向s[0]。
  2. 移动窗口右边界：将right指针右移，如果指向的字符ch是有效字符，那么counter_s[ch] += 1。如果字符ch的出现次数达标，那么valid += 1。
  3. 当我们得到一个可行窗口，即包含target的全部字母的窗口时:
     • 判断此时的子串是否长度更小。如果是，更新子串的起始位置start和长度minlen。
     • 移动窗口左边界：将left右移，如果离开的字符left_ch是有效字符，那么counter_s[left_ch] -= 1。如果字符left_ch的出现次数不再达标，那么valid -= 1。
     • 如果窗口依然可行，循环步骤3。否则，跳转至步骤2。

public static String minWindow(String source , String target) {
    // 初始化counter_s和counter_t
    Map<Character, Integer> counter_t = new HashMap<>();
    Map<Character, Integer> counter_s = new HashMap<>();
    for (int i = 0; i < target.length(); i++) {
        int count = counter_t.getOrDefault(target.charAt(i), 0);
        counter_t.put(target.charAt(i), count + 1);
    }

    int left = 0, valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    int start = -1, minlen = Integer.MAX_VALUE;
    for (int right = 0; right < source.length(); right ++){
        // 移动右边界, ch 是将移入窗口的字符
        char ch = source.charAt(right);
        // 如果counter_t里面包含source里的字符
        if (counter_t.containsKey(ch)) {
            // counter_s进行计数，注意，只有source中包含此字符，counter_s再进行计数
            counter_s.put(ch, counter_s.getOrDefault(ch, 0) + 1);
            // 对某个字符，只有counter_s和counter_t对其的计数一样，例如：counter_t中字符B出现3次，counter_s中字符B也出现3次，valid才加1
            if (counter_s.get(ch).equals(counter_t.get(ch))) {
                valid++;
            }
        }
        // 判断左侧窗口是否要收缩
        while (valid == counter_t.size()) {
            // 更新最小覆盖子串
            if (right - left < minlen) {
                start = left;
                minlen = right - left;
            }
            // left_ch 是将移出窗口的字符
            char left_ch = source.charAt(left);
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (counter_t.containsKey(left_ch)) {
                // 因为left_ch被移出去了，所以要判断下valid是否要减小
                if (counter_t.get(left_ch).equals(counter_s.get(left_ch))) {
                    valid--;
                }
                //之前的逻辑是：只有source中包含此字符，counter_s再进行计数，此时移除了，所以要减小counter_s的计数
                counter_s.put(left_ch, counter_s.getOrDefault(left_ch, 0) - 1);
            }
        }
    }
    // 返回最小覆盖子串
    return start == -1 ? "" : source.substring(start, start + minlen  + 1);
}