LeetCode -- Minimum Window Substring

LeetCode -- Minimum Window Substring

題目描述：
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).


For example,
S = ADOBECODEBANC
T = ABC
Minimum window is BANC.
Note:
If there is no such window in S that covers all characters in T, return the empty string .


If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.


本題就是要在串S中找到一個字串S[i...k]，其中i,k∈[0,n) ，n為S的長度，使得S[i...k]包含字符串T中的所有字符。




思路：
1. 使用hashT來保存每個字符出現的次數
2. 初始化hashS（將t的每個字符添加到hashS並將值初始化為0，即出現次數都為0），遍歷一次s（i∈[0,n)），對於s[i]：
2.1 如果s[i]在hashT中出現，將hashS[s[i]]累加，判斷hashS[s[i]]與hashT[s[i]]是否相等，即判斷此時是否完成了一次s[i]的映射，如果相等，將mapped變量（初始化為0）++
2.2 當完成了t中所有字符的映射時，即mapped = t中字符個數（不包含重復）時：
從當前窗口最左邊left(初始化為0)開始判斷：
如果hashT不包含s[left]：直接left++
如果hashT包含s[left]並且hashS[s[left]] 大於hashT[s[left]]，說明對s[left]的映射數量超出了所需要的個數hashT[s[left]]，此時也可以將left++。
此時判斷left到i的距離是否小於當前最小窗口，小於則更新窗口即可。




本題的實現參考了以下鏈接：
https://github.com/yuzhangcmu/LeetCode/blob/master/string/MinWindow.java
http://www.programcreek.com/2014/05/leetcode-minimum-window-substring-java/




實現代碼：

public class Solution {
    public string MinWindow(string s, string t) 
    {
        // 1. save t[i] into hash and get count of unique char in t
    	var countT = 0;
    	var hashT = new Dictionary();
    	for(var i = 0;i < t.Length; i++){
    		if(!hashT.ContainsKey(t[i])){
    			hashT.Add(t[i], 1);
    			countT++;
    		}
    		else{
    			hashT[t[i]]++;
    		}
    	}
    	
    	// 2. init hashS 
    	var hashS = new Dictionary();
    	for(var i = 0;i < s.Length; i++){
    		if(!hashS.ContainsKey(s[i])){
    			hashS.Add(s[i], 0);
    		}
    	}
    	
    	var mapped = 0; // without duplicate (say 'bccd' , mapped here means 'bcd')
    	var left = 0;
    	var minLen = s.Length;
    	var result = s;
    	
    	var found = false;
    	for (int i = 0; i < s.Length; i++) {
    		char c = s[i];
    		if (hashT.ContainsKey(c)) {
    			hashS[c]++;
    			// we have done mapping for s[i], increase mapped count for it
    			if (hashT[c] == hashS[c]) {
    				mapped++; 
    			}
    		}
    		
    		if (mapped == countT) 
    		{
    			found = true;
    			var leftC = s[left];
    			// if first char(say c) is not include in t , or count of c in hashS is more than in hashT then: hashS[c] -- 
    			// set left++
                while (!hashT.ContainsKey(leftC) || hashS[leftC] > hashT[leftC]){
                    if (hashT.ContainsKey(leftC) && hashS[leftC] > hashT[leftC]){
    					hashS[leftC]--;
    				}
                        
                    left++;
                    leftC = s[left];
                }
     
                if (i - left + 1< minLen) {
                    result = s.Substring(left, i - left + 1);
                    minLen = i - left + 1;
                }
    		}
        }
    	
    	return !found ?  : result;
    }
}