题解 | #最小覆盖子串#

• 使用双指针
• 满足覆盖条件时右移左指针缩小窗口
• 不满足覆盖条件时右移右指针扩大窗口

import java.util.*;
public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        int length = Integer.MAX_VALUE;
        String ans = "";
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> readyMap = new HashMap<>();
        Set<Character> set = new HashSet<>();
        Set<Character> readySet = new HashSet<>();
        for (int i = 0; i < T.length(); i++) {
            int oldValue = map.getOrDefault(T.charAt(i), 0);
            map.put(T.charAt(i), oldValue + 1);
            readyMap.put(T.charAt(i), 0);
            set.add(T.charAt(i));
        }
        int left = 0;
        int right = 0;
        while (right < S.length()) {
            if (readySet.size() < set.size()) {
                Character c = S.charAt(right);
                if (set.contains(c)) {
                    readyMap.put(c, readyMap.get(c) + 1);
                    if (readyMap.get(c) >= map.get(c)) {
                        readySet.add(c);
                    }
                }
                right++;
            }else {
                if (right - left < length) {
                    ans = S.substring(left, right);
                    length = ans.length();
                }
                Character c = S.charAt(left);
                if (set.contains(c)) {
                    readyMap.put(c, readyMap.get(c) - 1);
                    if (readyMap.get(c) < map.get(c) && readySet.contains(c)) {
                        readySet.remove(c);
                    }
                }
                left ++;
            }
        }
        while (readySet.size() == set.size()) {
            if (right - left < length) {
                ans = S.substring(left, right);
                length = ans.length();
            }
            Character c = S.charAt(left);
            if (set.contains(c)) {
                readyMap.put(c, readyMap.get(c) - 1);
                if (readyMap.get(c) < map.get(c) && readySet.contains(c)) {
                    readySet.remove(c);
                }
            }
            left ++;
        }
        return ans;
    }
}