Title Description:
You are given a string s, and a string t. Return the smallest substring of s that covers all the characters of t. If there is no substring of s that covers all the characters of t, the empty string "" is returned.
Attention:
For a duplicate character in t, the number of that character in the substring we are looking for must be no less than the number of that character in t.
If such a substring exists in s, we guarantee that it is the only answer.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: the minimal covering substring "BANC" contains 'A', 'B' and 'C' from string t.
Title Analysis:
When you see this type of longest and shortest substring, etc., then the sliding window approach is preferred. In accordance with the sliding window approach, the focus should be to determine the state of the window when the requirements are met: here is to contain all the elements of the string t can be, do not require ordered, then the use of a hash table to record is a good way, while the requirements of the shortest, that is, the subsequent to be optimized, because it is possible that the elements of T will be often repeated in the s, then the value of the hash table is set to the frequency of a very good way to reach the - -" elements appear, and the frequency once is the shortest state. Because it is a character, so the hash table is designed asvar targetFreq :=map[byte]int. Then the length of targetFreq represents the kind of elements in the target string.
Click to view code
func minWindow(s string, t string) string {
if len(s)==0 || len(t)==0{return ""}
left,right,matchCount:=0,0,0
start:=0
minLength := len(s)+1
targetFreq := make(map[byte]int)
for i := 0; i < len(t); i++ {
targetFreq[t[i]]++
}
windowFreq := make(map[byte]int)
for right<len(s){
charRight := s[right]
right++
if _,exists:=targetFreq[charRight];exists{
windowFreq[charRight]++
if windowFreq[charRight] == targetFreq[charRight] {
matchCount++
}
}
for matchCount == len(targetFreq){
// Trying to narrow the boundaries
if right-left <minLength{
minLength = right-left
start = left
}
charLeft:= s[left]
left++
if _,exists:=targetFreq[charLeft];exists{
if windowFreq[charLeft] == targetFreq[charLeft]{
matchCount--
}
windowFreq[charLeft]--
}
}
}
if minLength == len(s)+1{return ""}
return s[start:start+minLength]
}