Minimum Window Substring 32

Question

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Notice

If there is no such window in source that covers all characters in target, return the emtpy string "".

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

Clarification

Should the characters in minimum window has the same order in target?

Not necessary.

Example

For source = "ADOBECODEBANC", target = "ABC", the minimum window is "BANC"

Challenge

Can you do it in time complexity O(n) ?

Solution

1. 用一个数组Target（256长度，java中一共有256个字符）记录target中所有字符及其数量

2. 用sourceNum来记录source中和target中匹配上的字符数量，用两个指针left和right来表示当前子字符串的左右边界

3. 从左往右遍历source，每遇到一位字符，将Target中对应字符的数量－1，若Target中该字符的数量大于0，则表示该字符在target中，将sourceNum＋1

4. 当sourceNum和target长度相等时表明target中字符全部被当前子字符串匹配上，此时比较之前匹配上的子字符串长度，若当前子字符串较短，则更新最短子字符串长度和内容

5. 将当前子字符串左边界向右移1位，Target中对应字符（即原左边界字符）数量增加1，若Target中该字符数量大于0，则表示和target中匹配上的字符－1，否则只是删去多余字符，不影响

6. 当sourceNum小于target长度时，表示当前子字符串已经无法完全匹配target中字符，向右移动右边界，重复3-5步骤，寻找新的合适的子字符串，直到source遍历完成

代码如下：

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 source, String target) {
        // write your code
        int ans = Integer.MAX_VALUE;
        String minStr = "";

        //java一共有0-255个字符
        int[] Target = new int[256];

        //寻找target中有哪些字符并统计其个数，并返回target中字符长度
        int targetNum = initialTargetHash(Target, target);

        //sourceNum代表source中和target中匹配上的字符数，等于0的为target中没有的字符，大于0的表示target中有的字符的数量
        int sourceNum = 0;

        //left和right代表当前子字符串的左右边界
        int left = 0;
        int right = 0;

        for(; right < source.length(); right++){

            //Target中个数大于0的表示target中有的字符个数，若匹配上，则匹配数＋1
            if(Target[source.charAt(right)] > 0){
                sourceNum++;
            }

            //source中每增加一个字符会使Target中对应字符的数量－1，若小于0则表示source中的当前子字符串含有多余的字符（和target相比）
            Target[source.charAt(right)]--;

            //当匹配上的字符数大于等于target长度时，表示target中字符全部被匹配上
            while(sourceNum >= targetNum){

                //和之前的子字符串窗口的结果比较，寻找最小的子字符串窗口
                if(ans > right - left + 1){
                    ans = right - left + 1;
                    minStr = source.substring(left, right + 1);
                }

                //将当前子字符串左边界向右移1位，Target中相应字符数量增加1，若Target中该字符数量大于0，则表示和target中匹配上的字符－1，否则只是删去多余字符，不影响
                Target[source.charAt(left)]++;
                if(Target[source.charAt(left)] > 0){
                    sourceNum--;
                }
                left++;
            }
        }

        return minStr;
    }

    private int initialTargetHash(int[] Target, String target){
        int targetNum = 0;
        for(int i = 0; i < target.length(); i++){
            Target[target.charAt(i)]++;
            targetNum++;
        }
        return targetNum;
    }
}