Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 172
Good morning! Here's your coding interview problem for today.

This problem was asked by Dropbox.

Given a string s and a list of words `words`, where each word is the same length, find all starting indices of substrings in `s` that is a concatenation of every word in `words` exactly once.

For example, given `s = "dogcatcatcodecatdog"` and `words = ["cat", "dog"]`, return `[0, 13]`, since `"dogcat"` starts at index 0 and `"catdog"` starts at index 13.

Given `s = "barfoobazbitbyte"` and `words = ["dog", "cat"]`, return `[]` since there are no substrings composed of "dog" and "cat" in s.

The order of the indices does not matter.

Pull request description:
Day172
Resolves #358.

Patch:
diff --git a/README.md b/README.md
index e8f3088..7186829 100644
--- a/README.md
+++ b/README.md
@@ -183,3 +183,4 @@ problems from
 * [Day 169](https://github.com/vaskoz/dailycodingproblem-go/issues/352)
 * [Day 170](https://github.com/vaskoz/dailycodingproblem-go/issues/353)
 * [Day 171](https://github.com/vaskoz/dailycodingproblem-go/issues/356)
+* [Day 172](https://github.com/vaskoz/dailycodingproblem-go/issues/358)
diff --git a/day172/problem.go b/day172/problem.go
new file mode 100644
index 0000000..00d09b0
--- /dev/null
+++ b/day172/problem.go
@@ -0,0 +1,75 @@
+package day172
+
+type trie struct {
+	letters map[rune]*trie
+}
+
+func buildTrie(words []string) *trie {
+	t := &trie{make(map[rune]*trie)}
+	for _, word := range words {
+		curr := t
+		for _, r := range word {
+			if _, exists := curr.letters[r]; !exists {
+				curr.letters[r] = &trie{make(map[rune]*trie)}
+			}
+			curr = curr.letters[r]
+		}
+	}
+	return t
+}
+
+func buildWordIndicies(s string, try *trie, length int) []wordIndex {
+	var indicies []wordIndex
+	for i := range s {
+		curr := try
+		for j := i; j < i+length && j < len(s); j++ {
+			if _, found := curr.letters[rune(s[j])]; !found {
+				break
+			}
+			curr = curr.letters[rune(s[j])]
+		}
+		if len(curr.letters) == 0 {
+			indicies = append(indicies, wordIndex{s[i : i+length], i})
+		}
+	}
+	return indicies
+}
+
+type wordIndex struct {
+	word  string
+	index int
+}
+
+// ConcatenatedSubstringIndicies returns the starting indicies of substrings
+// composed of all the words provided.
+// Runs in O(k*N) time where N is the length of 's' and 'k' is the length
+// of each word in 'words'.
+func ConcatenatedSubstringIndicies(s string, words []string) []int {
+	try := buildTrie(words)
+	pos := make(map[string]int, len(words))
+	for i, word := range words {
+		pos[word] = i
+	}
+	length := len(words[0])
+	indicies := buildWordIndicies(s, try, length)
+	var result []int
+	for i, ind := range indicies {
+		w := make(map[string]struct{}, len(words))
+		w[ind.word] = struct{}{}
+		next := ind.index + length
+		for j := i + 1; j < len(indicies); j++ {
+			if indicies[j].index < next {
+				continue
+			} else if _, found := w[indicies[j].word]; found || indicies[j].index > next {
+				break
+			} else {
+				w[indicies[j].word] = struct{}{}
+				next += length
+			}
+		}
+		if len(w) == len(words) {
+			result = append(result, ind.index)
+		}
+	}
+	return result
+}


Test patch:
diff --git a/day172/problem_test.go b/day172/problem_test.go
new file mode 100644
index 0000000..81c7f1b
--- /dev/null
+++ b/day172/problem_test.go
@@ -0,0 +1,33 @@
+package day172
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	s        string
+	words    []string
+	expected []int
+}{
+	{"dogcatcatcodecatdog", []string{"cat", "dog"}, []int{0, 13}},
+	{"barfoobazbitbyte", []string{"dog", "cat"}, nil},
+	{"aabaa", []string{"aa", "ab"}, []int{1}},
+}
+
+func TestConcatenatedSubstringIndicies(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := ConcatenatedSubstringIndicies(tc.s, tc.words); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkConcatenatedSubstringIndicies(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ConcatenatedSubstringIndicies(tc.s, tc.words)
+		}
+	}
+}