Python describe LeetCode 76. Minimum cover substring

Hello everyone , I'm Qi Guanjie （qí guān jié ）, stay 【 Qi Guanjie 】 official account 、CSDN、GitHub、B Share some technical blog posts on the website and other platforms , It mainly includes front-end development 、python The backend development 、 Applet development 、 Data structure and algorithm 、docker、Linux Common operation and maintenance 、NLP And other related technical blog , Time flies , Future period , come on. ~

If you love bloggers, you can focus on the bloggers' official account. 【 Qi Guanjie 】(qí guān jié), The articles inside are more complete and updated faster . If you need to find a blogger, you can leave a message at the official account. , I will reply to the message as soon as possible .

---

This article was originally written as 【 Qi Guanjie 】（qí guān jié ）, Please support the original , Some platforms have been stealing blog articles maliciously ！！！ All articles please pay attention to WeChat official account 【 Qi Guanjie 】.

subject

Give you a string s 、 A string t . return s Covered by t The smallest string of all characters . If s There is no coverage in t Substring of all characters , Returns an empty string "" .

Be careful ：

• about t Duplicate characters in , The number of characters in the substring we are looking for must not be less than t The number of characters in the .
• If s There is such a substring in , We guarantee that it is 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 : ""
explain : t Two characters in 'a' Shall be included in s In the string of ,
Therefore, there is no qualified substring , Returns an empty string .

Tips ：

• 1 <= s.length, t.length <= 105
• s and t It's made up of English letters

** Advanced ：** You can design one in o(n) The algorithm to solve this problem in time ？

Their thinking

Double pointer ,O(n)

l,r Respectively represent the left and right of the current interval
r Go straight to the right , When we first find a sequence that can be satisfied , stop . Move l, Until the condition is not met , stay l The starting position of the shortest sequence satisfied by the update in the movement

Python describe

class Solution:
def minWindow(self, s: str, t: str) -> str:
def is_ok(sd, td):
for key, value in td.items():
if sd.get(key, 0) < value:
return False
return True
n, m = len(s), len(t)
if n < m:
return ""
td = {
}
sd = {
}
for i in range(m):
td[t[i]] = td.get(t[i], 0) + 1
sd[s[i]] = sd.get(s[i], 0) + 1
start = end = 0
if is_ok(sd, td):
start, end = 0, m
l, r = 0, m
while r < n:
sd[s[r]] = sd.get(s[r], 0) + 1
while is_ok(sd, td):
if end == 0 or r - l + 1 < end - start + 1:
start, end = l, r+1
sd[s[l]] -= 1
l += 1
r += 1
return s[start:end]