Python


  • 0
    def findNextValid(self, itr, cMap, chars, cnt, s):
        if s[itr] in cMap: 
            cMap[s[itr]] -= 1 
            if chars[s[itr]] > cMap[s[itr]]: cnt -= 1
        itr += 1
        while itr < len(s) and s[itr] not in cMap: 
            itr += 1
        return itr, cnt
            
    def minWindow(self, s, t):
        chars, cMap, cCnt, curr = {}, {}, 0, 0
        for c in t:
            chars[c] = chars.get(c,0) + 1
            cMap.setdefault(c,0)
            cCnt += 1
        i = j = 0
        minI, minJ = 0, len(s)
        while j < len(s):
            if curr == cCnt:
                while curr == cCnt:
                    if j-i < minJ-minI: minI, minJ = i, j
                    i, curr = self.findNextValid(i, cMap, chars, curr, s)
            else:
                if s[j] in cMap:
                    if cMap[s[j]] < chars[s[j]]: curr += 1
                    cMap[s[j]] += 1
                if curr == cCnt: continue
            j += 1
        return s[minI:minJ+1] if minJ < len(s) else ""

Log in to reply
 

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