https://leetcode-cn.com/problems/minimum-window-substring/

    1. class Solution {
    2.     public String minWindow(String s, String t) {
    3.            // 时间：O(N)
    4.         // 滑动窗口：枚举 s 中 可能覆盖 t 的子串
    5.         String resString = "";
    6.         // 定义一个 HashMap 保存频次
    7.         HashMap<Character, Integer> frequencyMap = new HashMap<>();
    8.         // 统计 t 中的字符
    9.         for (int i = 0; i < t.length(); i++) {
    10.             char c = t.charAt(i);
    11.             int count = frequencyMap.getOrDefault(c, 0);
    12.             frequencyMap.put(c, count + 1);
    13.         }
    14.         // 定义左右指针指向滑动窗口的起始、结束位置（左闭右开）
    15.         int start = 0, end = 1;
    16.         // 统计子串每个字符出现的频次
    17.         HashMap<Character, Integer> subStringFrequencyMap = new HashMap<>();
    19.         while (end <= s.length()) {
    20.             // end 增加之后，新增的字符
    21.             char newChar = s.charAt(end - 1);
    22.             // 新增字符频次加一
    23.             if (frequencyMap.containsKey(newChar)) {
    24.                 // t 串中有该字符才判断
    25.                 subStringFrequencyMap.put(newChar, subStringFrequencyMap.getOrDefault(newChar, 0) + 1);
    26.             }
    27.             // 如果当前子串符合覆盖子串要求，并且比之前的最小子串要短，就替换
    28.             while (check(frequencyMap, subStringFrequencyMap) && start < end) {
    29.                 if ((resString.equals("") || (end - start) < resString.length())) {
    30.                     resString = s.substring(start, end);
    31.                 }
    32.                 // 对要删除的字符频次减一
    33.                 char removeChar = s.charAt(start);
    34.                 if (frequencyMap.containsKey(removeChar)) {
    35.                     // t 串中有该字符才判断
    36.                     subStringFrequencyMap.put(removeChar, subStringFrequencyMap.getOrDefault(removeChar, 0) - 1);
    37.                 }
    38.                 // 不管是不是最小子串，左指针都需要移动，为了缩小窗口，寻找局部最优解
    39.                 start++;
    40.             }
    41.             // 不是覆盖子串，就要扩大窗口，寻找新的子串
    42.             end++;
    43.         }
    44.         return resString;
    45.     }
    47.         // 用于检查当前子串是否是一个覆盖 t 的子串
    48.     private boolean check(HashMap<Character, Integer> tFreq, HashMap<Character, Integer> subFreq) {
    49.         // 遍历 t 中每个字符的频次，与 subSting 进行比较
    50.         // 查看 t 中出现的每个字符在 subFreq 中出现的次数，一旦有不相等的情况出现（也不可能大于），就返回 false
    51.         for (Character character : tFreq.keySet()) {
    52.             if (subFreq.getOrDefault(character, 0) < tFreq.get(character)) {
    53.                 return false;
    54.             }
    55.         }
    56.         return true;
    57.     }
    58. }
    1. class Solution {
    2.     public String minWindow(String s, String t) {
    3.         // 时间：O(N)，但是实际会比上一个方法快得多
    4.         // 滑动窗口：枚举 s 中 可能覆盖 t 的子串
    5.         String resString = "";
    6.         // 定义一个 HashMap 保存频次
    7.         HashMap<Character, Integer> frequencyMap = new HashMap<>();
    8.         // 统计 t 中的字符
    9.         for (int i = 0; i < t.length(); i++) {
    10.             char c = t.charAt(i);
    11.             int count = frequencyMap.getOrDefault(c, 0);
    12.             frequencyMap.put(c, count + 1);
    13.         }
    14.         // 定义左右指针指向滑动窗口的起始、结束位置（左闭右开）
    15.         int start = 0, end = 1;
    16.         // 统计子串每个字符出现的频次
    17.         HashMap<Character, Integer> subStringFrequencyMap = new HashMap<>();
    18.         // 定义一个"贡献值"变量，统计 t 中的字符在子串中出现了多少
    19.         int targetCharCount = 0;
    21.         while (end <= s.length()) {
    22.             // end 增加之后，新增的字符
    23.             char newChar = s.charAt(end - 1);
    24.             // 新增字符频次加一
    25.             if (frequencyMap.containsKey(newChar)) {
    26.                 // t 串中有该字符才判断
    27.                 subStringFrequencyMap.put(newChar, subStringFrequencyMap.getOrDefault(newChar, 0) + 1);
    28.                 // 频次加一，还要看是否有贡献，如果子串中频次小于 t 中频次，当前字符就有贡献
    29.                 if (subStringFrequencyMap.get(newChar) <= frequencyMap.get(newChar)) {
    30.                     targetCharCount++;
    31.                 }
    32.             }
    33.             // 如果当前子串符合覆盖子串要求，即贡献值达到了 t 子串的数值。并且比之前的最小子串要短，就替换
    34.             while (targetCharCount == t.length() && start < end) {
    35.                 if ((resString.equals("") || (end - start) < resString.length())) {
    36.                     resString = s.substring(start, end);
    37.                 }
    38.                 // 对要删除的字符频次减一
    39.                 char removeChar = s.charAt(start);
    40.                 if (frequencyMap.containsKey(removeChar)) {
    41.                     // t 串中有该字符才判断
    42.                     subStringFrequencyMap.put(removeChar, subStringFrequencyMap.getOrDefault(removeChar, 0) - 1);
    43.                     // 如果子串中的频次不够 t 重的频次，此时相当于减少了一个真正有贡献的 char，贡献值减一
    44.                     if (subStringFrequencyMap.get(removeChar) < frequencyMap.get(removeChar)) {
    45.                         targetCharCount--;
    46.                     }
    47.                 }
    48.                 // 不管是不是最小子串，左指针都需要移动，为了缩小窗口，寻找局部最优解
    49.                 start++;
    50.             }
    51.             // 不是覆盖子串，就要扩大窗口，寻找新的子串
    52.             end++;
    53.         }
    54.         return resString;
    55.     }
    56. }
    class Solution {
    public String minWindow(String s, String t) {
String res = "";
        HashMap<Character, Integer> targetMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            targetMap.put(t.charAt(i), targetMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int start = 0, end = 1;
        HashMap<Character, Integer> subStringMap = new HashMap<>();
        int subStringCountVal = 0;
        while (end <= s.length()) {
            // 新增字符的操作
            char newChar = s.charAt(end - 1);
            if (targetMap.containsKey(newChar)) {
                subStringMap.put(newChar, subStringMap.getOrDefault(newChar, 0) + 1);
                // 遍历到到字串中到当前char的频次小于或等于目标字串中的频次时，都是有贡献的
                // 因为是目标字串中的频次值先加一
                if (subStringMap.get(newChar) <= targetMap.get(newChar)) {
                    subStringCountVal++;
                }
            }
            // 贡献值达到了才会有 start++ 的左缩减操作
            while (subStringCountVal == t.length() && start < end) {
                if (res.equals("") || (end - start) < res.length()) {
                    res = s.substring(start, end);
                }
                char removeChar = s.charAt(start);
                if (targetMap.containsKey(removeChar)) {
                    // 尝试缩减字符
                    subStringMap.put(removeChar, subStringMap.get(removeChar) - 1);
                    // 如果字符缩减之后，频次出现问题，贡献值变小
                    if (subStringMap.get(removeChar) < targetMap.get(removeChar)) {
                        subStringCountVal--;
                    }
                }
                start++;
            }
            end++;
        }
        return res;
    }
}