Minimum Window Substring

String, Two Pointers, Sliding Window

Hard

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 empty 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) ?

Tags

LinkedIn Hash Table Facebook

Analysis

可以用窗口型两个指针的思路来解决，外层for循环i = 0 ... n, 内层while循环，条件是j < source.length() 和 !isValid(sourceHash, targetHash)，前者是数组下标边界，后者是一个函数，检查当前窗口中的substring是否包含了目标字符串中全部所需的字符，未满足则继续扩大窗口j++，同时更新sourceHash。这里sourceHash，targetHash是整型数组int[]，因为ASCII码最多256个，因此用int[]可以作为简化的HashMap使用，key是char对应的int的值，value则是该char在substring中的出现个数。isValid函数则检查sourceHash是否全部包含了targetHash，256个字符一一对应，因此只需一重for循环，如果sourceHash[i] < targetHash[i]，则说明有字符未满足条件。

需要注意的是，要设定一个辅助变量记录minStr的长度。

1. Use two pointers: start and end to represent a window.
2. Move end to find a valid window.
3. When a valid window is found, move start to find a smaller window.

Solution

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) {
        if (source == null || source.length() == 0 ||
                target == null || target.length() == 0) {
            return "";
        }
        int[] sourceHash = new int[256];
        int[] targetHash = new int[256];
        int ans = Integer.MAX_VALUE;
        String minStr = "";

        initTargetHash(targetHash, target);

        int i = 0;
        int j = 0;

        for (i = 0; i < source.length(); i++) {
            while (j < source.length() && !isValid(sourceHash, targetHash)) {
                sourceHash[source.charAt(j)]++;
                if (j < source.length()) {
                    j++;
                } else {
                    break;
                }
            }
            if (isValid(sourceHash, targetHash)) {
                if (ans > j - i) {
                    ans = Math.min(ans, j - i);
                    minStr = source.substring(i, j);
                }
            }
            sourceHash[source.charAt(i)]--;
        }
        return minStr;
    }
    boolean isValid(int[] sourceHash, int[] targetHash) {
        for (int i = 0; i < sourceHash.length; i++) {
            if (targetHash[i] > sourceHash[i]) {
                return false;
            }
        }
        return true;
    }

    public void initTargetHash(int[] targetHash, String target) {
        for (int i = 0; i < target.length(); i++) {
            targetHash[target.charAt(i)]++;
        }
    }
}

Approach - Sliding Window - Two Pointer

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems/25848

public String minWindow(String s, String t) {
    HashMap<Character,Integer> map = new HashMap();
    for(char c : s.toCharArray())
        map.put(c,0);
    for(char c : t.toCharArray())
    {
        if(map.containsKey(c))
            map.put(c,map.get(c)+1);
        else
            return "";
    }

    int start =0, end=0, minStart=0,minLen = Integer.MAX_VALUE, counter = t.length();
    while(end < s.length())
    {
        char c1 = s.charAt(end);
        if(map.get(c1) > 0)
            counter--;
        map.put(c1,map.get(c1) - 1);

        end++;

        while(counter == 0)
        {
            if(minLen > end - start)
            {
                minLen = end - start;
                minStart = start;
            }

            char c2 = s.charAt(start);
            map.put(c2, map.get(c2) + 1);

            if(map.get(c2) > 0)
                counter++;

            start++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

Reference

Here is a 10-line template that can solve most 'substring' problems

[https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems](https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems)