Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 320
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a string, find the length of the smallest window that contains every distinct character. Characters may appear more than once in the window.

For example, given `"jiujitsu"`, you should return `5`, corresponding to the final five letters.

Pull request description:
Day320
Resolves #650.

Patch:
diff --git a/README.md b/README.md
index 3693706..ff0bd53 100644
--- a/README.md
+++ b/README.md
@@ -323,4 +323,5 @@ problems from
 * [Day 314](https://github.com/vaskoz/dailycodingproblem-go/issues/640)
 * [Day 315](https://github.com/vaskoz/dailycodingproblem-go/issues/642)
 * [Day 317](https://github.com/vaskoz/dailycodingproblem-go/issues/645)
+* [Day 320](https://github.com/vaskoz/dailycodingproblem-go/issues/650)
 * [Day 321](https://github.com/vaskoz/dailycodingproblem-go/issues/651)
diff --git a/day320/problem.go b/day320/problem.go
new file mode 100644
index 0000000..1773bc4
--- /dev/null
+++ b/day320/problem.go
@@ -0,0 +1,38 @@
+package day320
+
+// SmallestWindowEveryDistinctLength returns the length
+// of the smallest window that contains every distinct
+// character available.
+// Runs in O(N) time and O(k) extra space where k
+// is the number of distinct characters.
+func SmallestWindowEveryDistinctLength(str string) int {
+	distinct := make(map[rune]int)
+	for _, r := range str {
+		distinct[r]++
+	}
+	distinctCount := len(distinct)
+	distinct = make(map[rune]int, distinctCount)
+	var begin int
+	smallest := len(str)
+	for end, r := range str {
+		distinct[r]++
+		if len(distinct) == distinctCount {
+			for toRemove := rune(str[begin]); distinct[toRemove] > 1; toRemove = rune(str[begin]) {
+				distinct[toRemove]--
+				begin++
+			}
+			if length := end - begin + 1; length < smallest {
+				smallest = length
+			}
+		}
+		for len(distinct) == distinctCount {
+			toRemove := rune(str[begin])
+			distinct[toRemove]--
+			if count := distinct[toRemove]; count == 0 {
+				delete(distinct, toRemove)
+			}
+			begin++
+		}
+	}
+	return smallest
+}


Test patch:
diff --git a/day320/problem_test.go b/day320/problem_test.go
new file mode 100644
index 0000000..2aa483c
--- /dev/null
+++ b/day320/problem_test.go
@@ -0,0 +1,31 @@
+package day320
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	input        string
+	windowLength int
+}{
+	{"jiujitsu", 5},
+	{"", 0},
+	{"a", 1},
+	{"aabbccabaabbccc", 3},
+}
+
+func TestSmallestWindowEveryDistinctLength(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SmallestWindowEveryDistinctLength(tc.input); result != tc.windowLength {
+			t.Errorf("Expected %v, got %v", tc.windowLength, result)
+		}
+	}
+}
+
+func BenchmarkSmallestWindowEveryDistinctLength(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SmallestWindowEveryDistinctLength(tc.input)
+		}
+	}
+}