Python描述 LeetCode 76. 最小覆蓋子串

大家好，我是亓官劼（qí guān jié ），在【亓官劼】公眾號、CSDN、GitHub、B站等平台分享一些技術博文，主要包括前端開發、python後端開發、小程序開發、數據結構與算法、docker、Linux常用運維、NLP等相關技術博文，時光荏苒，未來可期，加油~

如果喜歡博主的文章可以關注博主的個人公眾號【亓官劼】(qí guān jié)，裡面的文章更全更新更快。如果有需要找博主的話可以在公眾號後台留言，我會盡快回復消息.

---

本文原創為【亓官劼】（qí guān jié ），請大家支持原創，部分平台一直在惡意盜取博主的文章！！！ 全部文章請關注微信公眾號【亓官劼】。

題目

給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。

注意：

• 對於 t 中重復字符，我們尋找的子字符串中該字符數量必須不少於 t 中該字符數量。
• 如果 s 中存在這樣的子串，我們保證它是唯一的答案。

示例 1：

輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"

示例 2：

輸入：s = "a", t = "a"
輸出："a"

示例 3:

輸入: s = "a", t = "aa"
輸出: ""
解釋: t 中兩個字符 'a' 均應包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母組成

**進階：**你能設計一個在 o(n) 時間內解決此問題的算法嗎？

解題思路

雙指針，O(n)

l,r分別表示當前區間的左右
r一直向右走，當第一次找到可以滿足的序列時，停下。移動l，直到不滿足條件位置，在l移動中更新滿足的最短序列的起始位置

Python描述

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]