Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 383
Good morning! Here's your coding interview problem for today.

This problem was asked by Gusto.

Implement the function `embolden(s, lst)` which takes in a string s and list of substrings `lst`, and wraps all substrings in `s` with an HTML bold tag `<b>` and `</b>`.

If two bold tags overlap or are contiguous, they should be merged.

For example, given `s = abcdefg` and `lst = ["bc", "ef"]`, return the string `a<b>bc</b>d<b>ef</b>g`.

Given `s = abcdefg` and `lst = ["bcd", "def"]`, return the string `a<b>bcdef</b>g`, since they overlap.

Pull request:
Day383
Resolves #772.

Patch:
diff --git a/README.md b/README.md
index 97e24a7..7c0bcf3 100644
--- a/README.md
+++ b/README.md
@@ -378,4 +378,5 @@ problems from
 * [Day 380](https://github.com/vaskoz/dailycodingproblem-go/issues/766)
 * [Day 381](https://github.com/vaskoz/dailycodingproblem-go/issues/768)
 * [Day 382](https://github.com/vaskoz/dailycodingproblem-go/issues/770)
+* [Day 383](https://github.com/vaskoz/dailycodingproblem-go/issues/772)
 
diff --git a/day383/problem.go b/day383/problem.go
new file mode 100644
index 0000000..655a9b3
--- /dev/null
+++ b/day383/problem.go
@@ -0,0 +1,79 @@
+package day383
+
+import (
+	"sort"
+	"strings"
+)
+
+type interval struct {
+	start, end int
+}
+
+// Embolden surrounds substrings (lst) in <b> tags
+// and combines overlapping substrings.
+func Embolden(s string, lst []string) string {
+	intervals := make([]interval, 0, len(lst))
+
+	for i := range lst {
+		pos := 0
+		for j := strings.Index(s[pos:], lst[i]); j != -1; j = strings.Index(s[pos:], lst[i]) {
+			pos += j
+			intervals = append(intervals, interval{pos, pos + len(lst[i])})
+			pos += len(lst[i])
+		}
+	}
+
+	sort.Slice(intervals, func(i, j int) bool {
+		if intervals[i].start < intervals[j].start {
+			return true
+		} else if intervals[i].start == intervals[j].start {
+			return intervals[i].end < intervals[j].end
+		}
+		return false
+	})
+
+	intervals = mergeIntervals(intervals)
+
+	var sb strings.Builder
+
+	pos := 0
+
+	for _, inter := range intervals {
+		sb.WriteString(s[pos:inter.start])
+		sb.WriteString("<b>")
+		sb.WriteString(s[inter.start:inter.end])
+		sb.WriteString("</b>")
+
+		pos = inter.end
+	}
+
+	sb.WriteString(s[pos:])
+
+	return sb.String()
+}
+
+func mergeIntervals(ints []interval) []interval {
+	merged := make([]interval, 0, len(ints))
+	merged = append(merged, ints[0])
+	last := 0
+
+	for i := 1; i < len(ints); i++ {
+		if ints[i].start > merged[last].start && ints[i].start < merged[last].end {
+			merged[last] = interval{merged[last].start,
+				max(merged[last].end, ints[i].end)}
+		} else {
+			merged = append(merged, ints[i])
+			last++
+		}
+	}
+
+	return merged
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+
+	return b
+}


Test patch:
diff --git a/day383/problem_test.go b/day383/problem_test.go
new file mode 100644
index 0000000..8ad73f3
--- /dev/null
+++ b/day383/problem_test.go
@@ -0,0 +1,34 @@
+package day383
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	s        string
+	lst      []string
+	expected string
+}{
+	{"abcdefg", []string{"bc", "ef"}, "a<b>bc</b>d<b>ef</b>g"},
+	{"abcdefg", []string{"bcd", "def"}, "a<b>bcdef</b>g"},
+	{"abcdefg", []string{"def", "bcd"}, "a<b>bcdef</b>g"},
+	{"abcdefg", []string{"def", "bcd", "defg"}, "a<b>bcdefg</b>"},
+	{"abcdefg", []string{"abcd", "bc"}, "<b>abcd</b>efg"},
+}
+
+func TestEmbolden(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res := Embolden(tc.s, tc.lst); res != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, res)
+		}
+	}
+}
+
+func BenchmarkEmbolden(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			Embolden(tc.s, tc.lst)
+		}
+	}
+}