题解 | #最小覆盖子串#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public string minWindow (string S, string T) {
        int left = 0, right = 0;
        Dictionary<char, int> dic = new Dictionary<char, int>();
        for(int i = 0; i < T.Length; i++){
            if(!dic.ContainsKey(T[i])) dic[T[i]] = 0;
            dic[T[i]]++;
        }
        int need = 0;
        int start = 0;
        int len = S.Length + 1;
        while(right < S.Length){
            //Console.WriteLine("right:"+right);
            if(dic.ContainsKey(S[right])){
                if(--dic[S[right]] == 0) need++;
            }
            while(need == dic.Count){
                if(right - left + 1 < len){
                    start = left;
                    len = right - left + 1;
                }
                if(dic.ContainsKey(S[left])){
                    if(dic[S[left]]++ == 0) need--;
                    //Console.Write("left:"+left+"need:"+need);
                }
                left++;
            }
            right++;
        }
        if(len == S.Length + 1) return "";
        return S.Substring(start, len);
    }
}