forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
76-Minimum-Window-Substring.go
39 lines (32 loc) · 914 Bytes
/
76-Minimum-Window-Substring.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func minWindow(s string, t string) string {
start, end := 0, 0
targetCharacterFrequency := make(map[uint8]int)
currentCharacterFrequency := make(map[uint8]int)
distinctCharacterCount := 0
minSubstring := ""
for index := range t {
targetCharacterFrequency[t[index]]++
}
for end < len(s) {
currentCharacterFrequency[s[end]]++
if targetCharacterFrequency[s[end]] != 0 &&
targetCharacterFrequency[s[end]] == currentCharacterFrequency[s[end]] {
distinctCharacterCount++
}
for distinctCharacterCount == len(targetCharacterFrequency) {
if minSubstring == "" {
minSubstring = s[start:end+1]
}
if end - start + 1 < len(minSubstring) {
minSubstring = s[start:end+1]
}
currentCharacterFrequency[s[start]]--
if currentCharacterFrequency[s[start]] < targetCharacterFrequency[s[start]] {
distinctCharacterCount--
}
start++
}
end++
}
return minSubstring
}