Python 20 lines AC O(n) solution


  • 5
    R

    Idea is pretty simple, keep two pointers left and right.

    If s[left:right] has all chars in T, calculate distance and keep answer, then move left pointer.

    If s[left:right] doesn't have all chars in T, move right pointer.

    class Solution:
    # @param {string} s
    # @param {string} t
    # @return {string}
    # sliding window problem
    # count all chars in string T
    # left pointer point to string which has been processed
    # right pointer point to string, which has not been processed
    # 1.if all window from left to right contains all string T(counter values all less then or equal to 0)
    #   calculate min window length, and keep answer
    #   then move left pointer
    # 2.else there are missing string in current answer
    #   move right pointer
    #   update counter
    # repeat 1, 2 steps until right is equal to len(s), then break it
    def minWindow(self, s, t):
        left, right = 0, 0
        # count T chars
        counter = collections.defaultdict(int)
        for a in t:
            counter[a] += 1
        
        minwindow = len(s) + 1
        answer = None
        
        while right <= len(s):
            # check all chars in T are in the current answer
            if all(map(lambda x: True if x<=0 else False, counter.values())):
                if minwindow > right-left:
                    minwindow = right-left
                    answer = s[left:right]
                char = s[left]
                if char in counter:
                    counter[char] += 1
                left += 1
            else:
                if right == len(s):
                    break
                char = s[right]
                if char in counter:
                    counter[char] -= 1
                right += 1
                
        return answer if answer else ''

  • 4
    W

    I think this is not O(n) since ' all(map(lambda x: True if x<=0 else False, counter.values())):' takes len(counter) steps.


  • 0
    D

    answer = s[left:right] takes O(right - left) time. So it is better to keep index instead of string slice


  • 0
    D

    I used your idea and implement an O(n) solution

    import sys
    class Solution(object):
        def minWindow(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: str
            """
            required, min_len = [0] * 128, sys.maxint
            # record numbers of each character in t
            for ch in t:
                required[ord(ch)] += 1
            left = right = min_start = 0
            # count: number of characters that are still required
            count = len(required) - required.count(0)
            while right < len(s):
                while count > 0 and right < len(s):
                    # move right till s[left : right] has all characters in t
                    required[ord(s[right])] -= 1
                    if required[ord(s[right])] == 0:
                        count -= 1
                    right += 1
                # s[left : right] has all characters in t, move left pointer
                while count == 0:
                    required[ord(s[left])] += 1
                    if required[ord(s[left])] == 1:
                        # now s[left : right] misses one character, update min_len if necessary
                        count = 1
                        if right - left < min_len:
                            min_len, min_start = right - left, left
                    left += 1
    
            return s[min_start : min_start+min_len] if min_len != sys.maxint else ''
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.