Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 103
Good morning! Here's your coding interview problem for today.

This problem was asked by Square.

Given a string and a set of characters, return the shortest substring containing all the characters in the set.

For example, given the string `"figehaeci"` and the set of characters `{a, e, i}`, you should return `"aeci"`.

If there is no substring containing all the characters in the set, return null.

Pull request description:
Day103
Resolves #217.

Patch:
diff --git a/README.md b/README.md
index cb56aaf..710675e 100644
--- a/README.md
+++ b/README.md
@@ -112,3 +112,4 @@ problems from
 * [Day 100](https://github.com/vaskoz/dailycodingproblem-go/issues/209)
 * [Day 101](https://github.com/vaskoz/dailycodingproblem-go/issues/212)
 * [Day 102](https://github.com/vaskoz/dailycodingproblem-go/issues/214)
+* [Day 103](https://github.com/vaskoz/dailycodingproblem-go/issues/217)
diff --git a/day103/problem.go b/day103/problem.go
new file mode 100644
index 0000000..b148f65
--- /dev/null
+++ b/day103/problem.go
@@ -0,0 +1,53 @@
+package day103
+
+// ShortestSubstringContains returns the shortest substring that contains
+// all the letters provided in any order.
+// Windowing runs in O(N) time and O(letters) extra space.
+func ShortestSubstringContains(str string, letters []rune) string {
+	occ := make(map[rune]int, len(letters))
+	for _, r := range letters {
+		occ[r]++
+	}
+	result := str
+	var start int
+	for end, r := range str {
+		if _, found := occ[r]; found {
+			occ[r]--
+			if allFound(occ) {
+				for {
+					if count, found := occ[rune(str[start])]; found && count+1 > 0 {
+						break
+					} else if found {
+						occ[rune(str[start])]++
+					}
+					start++
+				}
+				result = candidate(str[start:end+1], result)
+			}
+		}
+	}
+	return answer(result, !allFound(occ))
+}
+
+func answer(result string, notPossible bool) string {
+	if notPossible {
+		return ""
+	}
+	return result
+}
+
+func candidate(incumbent, challenger string) string {
+	if len(incumbent) <= len(challenger) {
+		return incumbent
+	}
+	return challenger
+}
+
+func allFound(m map[rune]int) bool {
+	for _, v := range m {
+		if v > 0 {
+			return false
+		}
+	}
+	return true
+}


Test patch:
diff --git a/day103/problem_test.go b/day103/problem_test.go
new file mode 100644
index 0000000..2c7fa7d
--- /dev/null
+++ b/day103/problem_test.go
@@ -0,0 +1,31 @@
+package day103
+
+import "testing"
+
+var testcases = []struct {
+	str      string
+	letters  []rune
+	expected string
+}{
+	{"figehaeci", []rune("aei"), "aeci"},
+	{"figehaeci", []rune("xei"), ""},
+	{"this is a test string", []rune("tist"), "t stri"},
+	{"a", []rune("ab"), ""},
+}
+
+func TestShortestSubstringContains(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := ShortestSubstringContains(tc.str, tc.letters); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkShortestSubstringContains(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ShortestSubstringContains(tc.str, tc.letters)
+		}
+	}
+}