题解 | #最小覆盖子串#TOP90

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
           // write code here

        int n = S.length();
        int m = T.length();
        //子串起点
        int start = 0;
        //子串长度 题目中长度小于10000
        int len = 10001;
        //统计T中字符出现的次数
        int[] map = new int[128];
        for (int i = 0; i < m; i++) {
            map[T.charAt(i)] ++;
        }
        //滑动窗口边界 l r  ，count 字符串数量
        int l = 0, r = 0, count = m;
        while ( r < n) {
            //如果在S出现次数大于0  向左找到能匹配的最大右边界
            //从左到右开始，直到不能 S中的字符在T中找不到为止
            if (map[S.charAt(r ++)]-- > 0) {
                count --;
            }

            while (count == 0) {
                //说明能找到了一个S的子串, 区间 [l, r-1]
                if (len > r - l) {
                    len = r - l;
                    start = l;
                }
                //相当于滑动窗口，将左侧位置后移一个数，这个数就往r 后找了
                if (map[S.charAt(l ++)]++ == 0) {
                    count ++;
                }
            }

        }
        return len == 10001 ? "" : S.substring(start,start +len);
    }
}