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)