0076. Minimum Window Substring

# 76. Minimum Window Substring#

## 题目 #

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

``````
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

``````

Note:

• If there is no such window in S that covers all characters in T, return the empty string “”.
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

## 代码 #

``````
package leetcode

func minWindow(s string, t string) string {
if s == "" || t == "" {
return ""
}
var tFreq, sFreq [256]int
result, left, right, finalLeft, finalRight, minW, count := "", 0, -1, -1, -1, len(s)+1, 0

for i := 0; i < len(t); i++ {
tFreq[t[i]-'a']++
}

for left < len(s) {
if right+1 < len(s) && count < len(t) {
sFreq[s[right+1]-'a']++
if sFreq[s[right+1]-'a'] <= tFreq[s[right+1]-'a'] {
count++
}
right++
} else {
if right-left+1 < minW && count == len(t) {
minW = right - left + 1
finalLeft = left
finalRight = right
}
if sFreq[s[left]-'a'] == tFreq[s[left]-'a'] {
count--
}
sFreq[s[left]-'a']--
left++
}
}
if finalLeft != -1 {
for i := finalLeft; i < finalRight+1; i++ {
result += string(s[i])
}
}
return result
}

``````

Sep 6, 2020