Minimum Window Substring

# Description

Given two strings `s` and `t` of lengths m and n respectively, return the minimum window substring of `s` such that every character in `t` (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is `unique`.

A substring is a contiguous sequence of characters within the string.

sliding Window

# Code

• submit code
``````class Solution:
def minWindow(self, s: str, t: str) -> str:
if(len(t) > len(s)):
return  ""

# create a need dict
need_dict = {}
for m in t:
need_dict[m] = need_dict.get(m,0) + 1

left = 0
right = 0
valid = 0
win_dict = {}

tmp_result = ""
result = ""
while left < len(s):
input = s[left]
left += 1

# updat Window
win_dict[input] = win_dict.get(input,0) + 1
tmp_result += input

if(need_dict.get(input)):
if(need_dict.get(input) == win_dict.get(input)):
valid += 1

#The time to decrease slide window？
while valid == len(need_dict):
if(len(tmp_result) < len(result) or result == ""):
result = tmp_result

output = s[right]
right += 1

win_dict[output] = win_dict.get(output) - 1
if(win_dict.get(output,0) < need_dict.get(output,0)):
valid -= 1
tmp_result = tmp_result[1:] # Delete The First Character

return result
``````
• Full Code
``````class Solution:
def minWindow(self, s: str, t: str) -> str:

if(len(t) > len(s)):
return  ""

# 构造需求字典
need_dict = {}
for m in t:
need_dict[m] = need_dict.get(m,0) + 1

left = 0
right = 0
valid = 0
print(need_dict)
win_dict = {}

tmp_result = ""
result = ""
while left < len(s):
input = s[left]
left += 1

# 窗口数据字典更新
win_dict[input] = win_dict.get(input,0) + 1
tmp_result += input # 窗口字符串
# print("tmp_result",tmp_result)

# 需求字典有效值判断
if(need_dict.get(input)):
if(need_dict.get(input) == win_dict.get(input)):
valid += 1
# print(win_dict)

# 缩小的条件是啥？
# 窗口中的字符串满足需要的基本数据，但不一定是最小的字符串
while valid == len(need_dict):
print("valid: " + str(valid) + "\tneed: " + str(need_dict))
print("tmp_result " + str(tmp_result))
# 更新result为长度最小的字符串
# 及求取最优节
if(len(tmp_result) < len(result) or result == ""):
result = tmp_result

output = s[right]
right += 1

win_dict[output] = win_dict.get(output) - 1
if(win_dict.get(output,0) < need_dict.get(output,0)):
valid -= 1
tmp_result = tmp_result[1:] # 删除第一个字符
print("\n#################################")
print(tmp_result)

return result

S = Solution()
t = "ABC"
# s = "a"
# t = "a"
print("result",S.minWindow(s,t))

# print("******************")
# print(s[1:])
``````

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2022/02/26/minimum-window-substring-2/``

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安