Minimum Window Substring

Problem: Minimum Window Substring

For this problem, we assume a window with undefined size that slides through the string. Once the window met a target character, the window "eat"s the character and begins to grow until there are no more needed target characters. However, to get the minimum window, we still need to search further for better options.

For example, in "ADOBECODEBANC", we get window as "ADOBEC" first. When we look at the 2nd "B", we get window as "ADOBECODEB", we cannot trim our result window or we will lose an "A". When we get "ADOBECODEBA", we can now trim "ADO" from our string, because "D" and "O" are never needed. Then we found that we can also trim "BE" since we've got two "B"s in our result. We can repeat this kind of process to get "BANC" as our result.

To conclude, there are two values we care about. One is the necessity of characters. If the character is not needed, we can trim as we want. The other is whether there are missing targets. If all the targets are already in the result, then we can start considering trimming. Of course, the size of the result is also important.

Code in Python:

import collections

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        i = I = J = 0
        missing = len(t)
        need = collections.Counter(t)
        for j, c in enumerate(s, 1):
            missing -= need[c] > 0
            need[c] -= 1
            if not missing:
                while need[s[i]] < 0 and i < j:
                    need[s[i]] += 1
                    i += 1
                if j-i <= J-I or not J:
                    I, J = i, j

        return s[I:J]

Details:

• Use index to represent sliding window, do not use separate list and string
• Python's enumerate function
• Python's collection.Counter