The sliding window algorithm matches character substrings

Reference: Sliding Window Algorithm analysis and practice

Example: Minimum coverage substring

Given a string S and a string T, find the smallest string in S that contains all the letters of T.

Example: input: S = “ADOBECODEBANC”, T = “ABC” output: “BANC”

class Solution:
    def minWindow(self, s: str, t: str) - >str:
        if len(t) > len(s):
            return ""
        if len(t) is None or len(s) is None:
            return ""
        
        # Count the number of characters and the total length of the string
        t_dict = {}
        ABC = "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM"
        
        count = 0
        for char in ABC:
            n = t.count(char)
            if n > 0:
                t_dict[char] = n
                count += n
        
        Record the smallest result subscript and length
        min_begin = -1
        min_end = -1
        min_num = -1
        
        Record the subscript of the character t in the s string
        index = []
        Record the values of the characters related to t in the s string
        strlist = []
        # temporary variable, subscript of character
        i = 0
        
        for char in s:
            if char in t_dict.keys():
                strlist.append(char)
                index.append(i)
            i += 1
            
        The length of the character set associated with t is less than the length of t
        Return if no match is found
        length = len(t)
        # Record the length of the s string relative to t
        str_len = len(strlist)
        if str_len < length:
            return ""
            
        begin = 0
        end = 0 
        max_begin = str_len - length
        
        while end <= str_len and begin <= max_begin:
            isOK = True         Record whether the match was successful
            if end - begin < length:
                isOK = False
            else:
                if count > 0 :
                    isOK = False
                else:
                    pass
                
            if isOK:
                # match successful, record subscript and length
                num = index[end-1] - index[begin]
                if num < min_num or min_num == -1:
                    min_begin = begin
                    min_end = end-1
                    min_num = num
                    
                The string header pointer moves forward
                # Attempt a successful match with a shorter length
                k = strlist[begin]
                t_dict[k] += 1
                if t_dict[k] > 0:
                    count += 1 
                begin += 1
            else:
                # failed to match, end of string pointer moved forward
                if end < str_len:
                    end += 1
                    k = strlist[end - 1]
                    t_dict[k] -= 1
                    if t_dict[k] >= 0:
                        count -= 1 
                else:
                The tail pointer already points to the last bit of the string
                # The header pointer advances until begin <= max_BEGIN attempts a successful match with a shorter length
                    k = strlist[begin]
                    t_dict[k] += 1
                    if t_dict[k] > 0:
                        count += 1 
                    begin += 1
        
        If the match is successful, the result is returned
        ifmin_num ! = -1:
            start = index[min_begin]
            end = index[min_end] + 1
            return s[start: end]
        else:
            return ""
Copy the code