leetcode/含有所有字符的最短字符串

package com.xcrj;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;


public class Solution17 {
    // Map<字符,出现次数>
    private Map tmap = new HashMap<>();
    //
    private Map smap = new HashMap<>();

    
    public String minWindow1(String s, String t) {
        // 特殊情况
        if (s.length() < t.length()) {
            return "";
        }

        // 统计t中字符
        for (char c : t.toCharArray()) {
            tmap.put(c, tmap.getOrDefault(c, 0) + 1);
        }

        int minLen = Integer.MAX_VALUE;
        int start = 0;
        int l = 0;
        int r = -1;
        // ！！！记住这个滑动窗口的双wihle模板代码
        while (r < s.length()) {
            // 右移r：r不停的右移，直到l~r的字符都包含在t中
            r++;
            if (r < s.length() && tmap.containsKey(s.charAt(r))) {
                // 统计t包含 s字符串的l~r字符
                smap.put(s.charAt(r), smap.getOrDefault(s.charAt(r), 0) + 1);
            }
            // 右移l：检查l~r的s子串中的每个字符的数量>=t中每个字符的数量，尝试右移l
            while (l <= r && check1()) {
                // 右移l过程中判断最小长度
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    start = l;
                }
                // 统计，剔除l指向的s中的字符
                if (smap.containsKey(s.charAt(l))) {
                    smap.put(s.charAt(l), smap.get(s.charAt(l)) - 1);
                }
                l++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    
    public boolean check1() {
        for (Map.Entry tentry : tmap.entrySet()) {
            // l~r在smap中统计的字符数量 一定要>= tmap统计的字符数量，如果小于则不满足 s(l~r)要包含t中所有字符的条件，如果>则存在右移的机会
            if (smap.getOrDefault(tentry.getKey(), 0) < tentry.getValue()) {
                return false;
            }
        }
        // l~r的s子串中的每个字符的数量>=t中每个字符的数量
        return true;
    }

    public static void main(String[] args) {
        Solution17 solution17 = new Solution17();
        System.out.println(solution17.minWindow1("a", "b"));
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/M1oyTv/solution/han-you-suo-you-zi-fu-de-zui-duan-zi-fu-a8q50/
来源：力扣（LeetCode）