Title address (76. Minimum coverage substring)

Leetcode-cn.com/problems/mi…

Topic describes

I give you a string S, a string t. Returns the smallest string in S that covers all characters of t. Return an empty string "" if there is no substring in S that covers all characters of t. Note: For repeated characters in t, we must look for substrings that have at least the number of characters in t. If such a substring exists in s, we guarantee that it's the only answer. Example 1: input: s = "ADOBECODEBANC", t = "ABC" output: "BANC" example 2: input: s = "a", t = "a" output: "a" example 3: input: s = "a", t = "aa" output: "" Explanation: both characters 'a' in t should be contained in the substring of S, so there is no qualified substring, return empty string. Tip: 1 <= s.length, t.length <= 105 s and T are composed of English letters Advanced: Can you design an algorithm to solve this problem in O (n) time?Copy the code

Train of thought

The sliding window expands on the right, and after satisfying the string traversal condition, the left side shrinks. The difficulty lies in the boundary condition of the left side contraction

code

  • Language support: Python3

Python3 Code:


class Solution:
    def minWindow(self, s: str, t: str) - >str:
        from collections import Counter
        length = len(s)
        left,right,match = 0.0.0
        resLeft,resRight,minResLen = 0.0,length+1
        tDict = Counter(t)
        while right < length:
            # expand to the right first
            # print(left, right, resLeft, resRight)
            # print([s[left:right+1]])
            rS = s[right]
            # print(rS,tDict)
            if rS in tDict:
                tDict[rS] -= 1
                if tDict[rS] >= 0:
                    match += 1
            # Contraction condition
            while match == len(t):
                Determine the shortest substring length
                if (right - left) < minResLen:
                    # print([s[left:right + 1]],resRight,resLeft, minResLen)
                    minResLen = min(minResLen,right-left)
                    resLeft,resRight = left,right
                # The left side is shrinking until mtath
                if left <= right:
                    lS = s[left]
                    if lS in tDict:
                        tDict[lS] += 1
                        if tDict[lS] > 0:
                            match -= 1
                        # print(lS, tDict)
                    left += 1
            right += 1
        # print(left, right, resLeft, resRight)
        return s[resLeft:resRight+1] ifminResLen ! = length+1 else ""

if __name__ == '__main__':
    s = "ADOBECODEBANC"
    t = "ABC"
    s = "a"
    t = "a"
    result = Solution().minWindow(s,t)
    print(result)

Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)