【題目描述】

給定兩個字符串 source 和 target. 求 source 中最短的包含 target 中每一個字符的子串.
1.如果沒有答案, 返回 "".
2.保證答案是唯一的.
3.target 可能包含重復的字符, 而你的答案需要包含至少相同數量的該字符.

【題目樣例】

樣例 1:

輸入: source = "abc", target = "ac"
輸出: "abc"

樣例 2:

輸入: source = "adobecodebanc", target = "abc"
輸出: "banc"
解釋: "banc" 是 source 的包含 target 的每一個字符的最短的子串.

樣例 3:

輸入: source = "abc", target = "aa"
輸出: ""
解釋: 沒有子串包含兩個 'a'.

【評測與題解】

→戳這里在線評測及查看題解

/**
* 本參考程序來自九章算法，由 @九章算法 提供。版權所有，轉發(fā)請注明出處。
* - 九章算法致力于幫助更多中國人找到好的工作，教師團隊均來自硅谷和國內的一線大公司在職工程師。
* - 現(xiàn)有的面試培訓課程包括：九章算法班，系統(tǒng)設計班，算法強化班，Java入門與基礎算法班，Android 項目實戰(zhàn)班，
* - Big Data 項目實戰(zhàn)班，算法面試高頻題班, 動態(tài)規(guī)劃專題班
* - 更多詳情請見官方網站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param source : A string
     * @param target: A string
     * @return: A string denote the minimum window, return "" if there is no such a string
     */
    public String minWindow(String ss , String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        if (t.length == 0) {
            return "";
        }
        
        int[] cntS = new int[256]; // number of appearances for each character in the window
        int[] cntT = new int[256]; // how many times each character appears in T
        int K = 0; // number of T's unique chracters
        for (int i = 0; i < 256; ++i) {
            cntS[i] = cntT[i] = 0;
        }
        
        for (char c : t) {
            ++cntT[c];
            if (cntT[c] == 1) {
                ++K;
            }
        }
        
        // abccba ==> K=3
        int now = 0; // number of T's unique characters the window contains
        // when now == K, we're good
        
        int ansl = -1, ansr = -1;
        int l, r = 0;
        for (l = 0; l < s.length; ++l) { // main pointer, st
            // insert into window
            while (r < s.length && now < K) {
                ++cntS[s[r]];
                // phase jump
                if (cntS[s[r]] == cntT[s[r]]) {
                    ++now;
                }
                
                ++r;
            }
            
            if (now == K) {
                // this window is good
                if (ansl == -1 || r - l < ansr - ansl) {
                    ansl = l;
                    ansr = r;
                }
            }
            
            // remove from window
            --cntS[s[l]];
            if (cntS[s[l]] == cntT[s[l]] - 1) {
                --now;
            }
        }
        
        // s[l...(r-1)]
        if (ansl == -1) {
            return "";
        }
        else {
            return ss.substring(ansl, ansr);
        }
    }
}