题解 | #最小覆盖子串#

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        if (S == null || T == null) {
            return S == null ? S : T;
        }
        char[] sArr = S.toCharArray();
        char[] tArr = T.toCharArray();
        int sLen = sArr.length;
        int tLen = tArr.length;
        if (sLen < tLen) {
            return "";
        }
        int[] hash = new int[128];
        for (char ch : tArr) {
            hash[ch]--;
        }
        int slow = 0;
        int fast = 0;
        int left = -1;
        int right = -1;
        int min = sLen + 1;
        while (fast < sLen) {
            char ch = sArr[fast];
            hash[ch]++;
            while (check(hash)) {
                if (fast - slow + 1 < min) {
                    min = fast - slow + 1;
                    left = slow;
                    right = fast;
                }
                hash[sArr[slow]]--;
                slow++;
            }
            fast++;
        }
        if (left == -1) {
            return "";
        }
        return S.substring(left, right + 1);
    }

    private boolean check(int[] hash) {
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] < 0) {
                return false;
            }
        } 
        return true;
    }
}