Second solution. Intuition is to open the window until character frequencies in t are all less than zero. After, close the window until any single character frequency of t is larger than 0.
(s string, t string)
| 5 | // After, close the window until any single character frequency |
| 6 | // of t is larger than 0. |
| 7 | func minWindow(s string, t string) string { |
| 8 | // create a map from character it's frequency in t |
| 9 | tmap := make(map[string]int) |
| 10 | for _, r := range t { |
| 11 | tmap[string(r)] += 1 |
| 12 | } |
| 13 | |
| 14 | var min string |
| 15 | var start, end int |
| 16 | for start < len(s) && end < len(s) { |
| 17 | _, ok := tmap[string(s[end])] |
| 18 | if ok { |
| 19 | tmap[string(s[end])]-- |
| 20 | |
| 21 | // shrink start of window until window does not contain |
| 22 | // every character in t |
| 23 | for mapValuesLessThanOne(tmap) { |
| 24 | // set the new min if it's smaller than old min |
| 25 | if min == "" || len(min) > len(s[start:end+1]) { |
| 26 | min = s[start : end+1] |
| 27 | } |
| 28 | |
| 29 | // if s[start] is in tmap, increment it's count for removal |
| 30 | _, ok := tmap[string(s[start])] |
| 31 | if ok { |
| 32 | tmap[string(s[start])]++ |
| 33 | } |
| 34 | |
| 35 | // shrink the start of the window |
| 36 | start++ |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | end++ |
| 41 | } |
| 42 | |
| 43 | return min |
| 44 | } |
| 45 | |
| 46 | func mapValuesLessThanOne(m map[string]int) bool { |
| 47 | for _, v := range m { |