76.Minimum Window Substring

Tags: [string], [two_pointer], [map], [window], [shrink_window]

Com: {fb}

Link: https://leetcode.com/problems/minimum-window-substring/\#/description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S="ADOBECODEBANC"
T="ABC"

Minimum window is"BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string"".

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

Solution: Two Pointers, Shrink Window

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not s or not t or len(s) < len(t):
            return ''

        num_of_missing_chars = 0
        need_chars = {}
        for c in t:
            num_of_missing_chars += 1
            if c not in need_chars:
                need_chars[c] = 1
            else:
                need_chars[c] += 1

        min_win_size = len(s) + 1
        min_win_start = -1
        min_win_end = -1

        start = 0
        end = 0

        while end < len(s):
            curr = s[end]
            if num_of_missing_chars > 0:
                # continue moving the end pointer to right, to collect more chars.
                if curr in need_chars:
                    if need_chars[curr] > 0:
                        num_of_missing_chars -= 1

                    need_chars[curr] -= 1

            if num_of_missing_chars == 0:
                # shrink the window, by moving the start pointer to right.
                while start <= end:
                    curr_start = s[start]
                    if curr_start in need_chars:
                        if need_chars[curr_start] == 0:
                            break
                        elif need_chars[curr_start] < 0:
                            need_chars[curr_start] += 1

                    start += 1

                curr_win_size = end - start + 1
                if curr_win_size < min_win_size:
                    min_win_size = curr_win_size
                    min_win_start = start
                    min_win_end = end

                num_of_missing_chars += 1
                need_chars[s[start]] += 1
                start += 1

            end += 1

        if min_win_start < 0:
            return ''
        else:
            return s[min_win_start:min_win_end + 1]

Revelation:

• Do not try to recall the previous problem, meet one problem, just use the current knowledge to solve it.
• The 'num_of_missing_chars' is recording the real number of chars we still need.
• The value of need_chars[c] can be positive, zero and negative. If the value is negative, it means you have collected more chars than you need in the current window.

Note:

• Time complexity = O(n), n is the length of the given string s.