Initial solution. Pretty close, but overly complicated and assumed that duplicates of t were not allowed, meaning the substring of s must have exactly (and no more) the same frequency of unique characters in t.
(s string, t string)
| 57 | // the substring of s must have exactly (and no more) the same |
| 58 | // frequency of unique characters in t. |
| 59 | func minWindow0(s string, t string) string { |
| 60 | tmap := make(map[string]int) |
| 61 | for _, r := range t { |
| 62 | tmap[string(r)] += 1 |
| 63 | } |
| 64 | |
| 65 | // move i forward until a character in tmap is seen |
| 66 | var i, j int |
| 67 | for i = 0; i < len(s); i++ { |
| 68 | _, ok := tmap[string(s[i])] |
| 69 | if ok { |
| 70 | break |
| 71 | } |
| 72 | } |
| 73 | j = i |
| 74 | |
| 75 | min := "" |
| 76 | for i < len(s) && j < len(s) { |
| 77 | _, ok := tmap[string(s[j])] |
| 78 | if ok { |
| 79 | tmap[string(s[j])]-- |
| 80 | |
| 81 | if tmap[string(s[j])] < 0 { |
| 82 | for tmap[string(s[j])] < 0 { |
| 83 | _, ok := tmap[string(s[i])] |
| 84 | if ok { |
| 85 | tmap[string(s[i])]++ |
| 86 | } |
| 87 | i++ |
| 88 | } |
| 89 | _, ok := tmap[string(s[i])] |
| 90 | for !ok { |
| 91 | i++ |
| 92 | _, ok = tmap[string(s[i])] |
| 93 | } |
| 94 | } |
| 95 | |
| 96 | allLessThanZero := true |
| 97 | for _, v := range tmap { |
| 98 | if v != 0 { |
| 99 | allLessThanZero = false |
| 100 | } |
| 101 | } |
| 102 | |
| 103 | if allLessThanZero { |
| 104 | if min == "" || len(min) > len(s[i:j+1]) { |
| 105 | min = s[i : j+1] |
| 106 | } |
| 107 | tmap[string(s[i])]++ |
| 108 | |
| 109 | // move i forward until a character in tmap is seen |
| 110 | i++ |
| 111 | if i < len(s) { |
| 112 | _, ok := tmap[string(s[i])] |
| 113 | for !ok { |
| 114 | i++ |
| 115 | _, ok = tmap[string(s[i])] |
| 116 | } |
nothing calls this directly
no outgoing calls
no test coverage detected