True O(n) solution with Bit Manipulation & Two Pointers & Hashmap


  • 0
    class Solution(object):
        def minWindow(self, s, t):
            rs, rt = collections.defaultdict(int), collections.Counter(t)
            destS, destT = 0, reduce(operator.or_, (1 << ord(c) - 65 for c in t))
    
            head, tail, start, end = 0, 0, float('-inf'), float('inf')
            while 1:
                while head < len(s) and destS != destT:
                    char = s[head]
                    rs[char] += 1
    
                    if char in rt and rs[char] >= rt[char]:
                        destS |= 1 << ord(char) - 65
    
                    head += 1
    
                if head >= len(s) and destS != destT:
                    break
    
                while tail < head and destS == destT:
                    char = s[tail]
                    rs[char] -= 1
    
                    if head - tail < end - start:
                        start, end = tail, head
    
                    if char in rt and rs[char] < rt[char]:
                        destS &= ~(1 << ord(char) - 65)
    
                    tail += 1
    
            return s[start:end] if end != float('inf') else ''

Log in to reply
 

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