96 lines
1.5 KiB
Go
96 lines
1.5 KiB
Go
package minimumwindowsubstring
|
|
|
|
import "fmt"
|
|
|
|
type Set[T comparable] map[T]int
|
|
|
|
type Substring struct {
|
|
Main string
|
|
Left int
|
|
Right int
|
|
Set Set[byte]
|
|
}
|
|
|
|
func Better(a, b string) string {
|
|
if len(a) == 0 {
|
|
return b
|
|
} else if len(b) < len(a) {
|
|
return b
|
|
}
|
|
|
|
return a
|
|
}
|
|
|
|
func NewSubstring(s string) Substring {
|
|
return Substring{s, 0, len(s) - 1, NewSet(s)}
|
|
}
|
|
|
|
func (s Set[T]) SubsetOf(t Set[T]) bool {
|
|
for k := range s {
|
|
if s[k] > t[k] {
|
|
return false
|
|
}
|
|
}
|
|
|
|
return true
|
|
}
|
|
|
|
func NewSet(t string) Set[byte] {
|
|
set := Set[byte]{}
|
|
for i := range t {
|
|
set[t[i]]++
|
|
}
|
|
|
|
return set
|
|
}
|
|
|
|
func (s *Substring) CullLeft(t Substring) {
|
|
for s.Set[s.Main[s.Left]] > t.Set[s.Main[s.Left]] {
|
|
s.Set[s.Main[s.Left]]--
|
|
s.Left++
|
|
}
|
|
|
|
fmt.Println("CANNOT CULL", string(s.Main[s.Left]))
|
|
}
|
|
|
|
func (s *Substring) IncRight() bool {
|
|
if s.Right == len(s.Main)-1 {
|
|
return false
|
|
}
|
|
|
|
s.Right++
|
|
s.Set[s.Main[s.Right]]++
|
|
return true
|
|
}
|
|
|
|
func (s Substring) String() string {
|
|
return s.Main[s.Left : s.Right+1]
|
|
}
|
|
|
|
func (s *Substring) CullRight(t Substring) {
|
|
for s.Set[s.Main[s.Right]] > t.Set[s.Main[s.Right]] {
|
|
s.Set[s.Main[s.Right]]--
|
|
s.Right--
|
|
}
|
|
}
|
|
|
|
func minWindow(s string, t string) string {
|
|
ss, tt := NewSubstring(s), NewSubstring(t)
|
|
best_answer := ""
|
|
|
|
if !tt.Set.SubsetOf(ss.Set) {
|
|
return best_answer
|
|
}
|
|
|
|
ss.CullRight(tt)
|
|
ss.CullLeft(tt)
|
|
best_answer = Better(best_answer, ss.String())
|
|
|
|
for ss.IncRight() {
|
|
ss.CullLeft(tt)
|
|
best_answer = Better(best_answer, ss.String())
|
|
}
|
|
|
|
return best_answer
|
|
}
|