LintCode题解 | 谷歌面试真题：最小子串覆盖

【题目描述】

给定两个字符串 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'.

【评测与题解】

→戳这里在线评测及查看题解

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：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);
        }
    }
}