Minimum Window Substring

Question

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

Example source = "ADOBECODEBANC" target = "ABC" Minimum window is "BANC".

Note 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.

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

Thoughts

two pointer类题目

注意点：

• j index 是否包括
• 重复元素的次数统计

Solution

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
    """
    def minWindow(self, source, target):
        # write your code here
        if not target:
            return ""
        if not source:
            return ""
        sourceMap = {}
        targetMap = {}
        for t in target:
            if t in targetMap:
                targetMap[t] += 1
            else:
                targetMap[t] = 1
        result = ""

        j = 0
        for i in range(len(source)):
            while j < len(source) and not self.containsAll(sourceMap, targetMap):
                if source[j] not in sourceMap:
                    sourceMap[source[j]] = 1
                else:
                    sourceMap[source[j]] += 1
                j += 1
            if self.containsAll(sourceMap, targetMap):
                if result:
                    if len(result) > len(source[i:j]):
                        result = source[i:j]
                else:
                    result = source[i:j]
            sourceMap[source[i]] -= 1

        return result

    def containsAll(self, sourceMap, targetMap):
        for t in targetMap:
            if t not in sourceMap:
                return False
            #should be less than
            if sourceMap[t] < targetMap[t]:
                return False
        return True