Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 34
Good morning! Here's your coding interview problem for today.

This problem was asked by Quora.

Given a string, find the palindrome that can be made by inserting the fewest number of characters as possible anywhere in the word. If there is more than one palindrome of minimum length that can be made, return the lexicographically earliest one (the first one alphabetically).

For example, given the string "race", you should return "ecarace", since we can add three letters to it (which is the smallest amount to make a palindrome). There are seven other palindromes that can be made from "race" by adding three letters, but "ecarace" comes first alphabetically.

As another example, given the string "google", you should return "elgoogle".

Pull request:
Day34
Resolves #76 .

Patch:
diff --git a/README.md b/README.md
index 36552d1..4ec99d9 100644
--- a/README.md
+++ b/README.md
@@ -45,6 +45,7 @@ problems from
 * [Day 30](https://github.com/vaskoz/dailycodingproblem-go/issues/69)
 * [Day 31](https://github.com/vaskoz/dailycodingproblem-go/issues/71)
 * [Day 33](https://github.com/vaskoz/dailycodingproblem-go/issues/73)
+* [Day 34](https://github.com/vaskoz/dailycodingproblem-go/issues/76)
 * [Day 35](https://github.com/vaskoz/dailycodingproblem-go/issues/77)
 * [Day 36](https://github.com/vaskoz/dailycodingproblem-go/issues/79)
 * [Day 37](https://github.com/vaskoz/dailycodingproblem-go/issues/81)
diff --git a/day34/problem.go b/day34/problem.go
new file mode 100644
index 0000000..45bf6b9
--- /dev/null
+++ b/day34/problem.go
@@ -0,0 +1,49 @@
+package day34
+
+// MakePalindrome calculates the minimum number of insertions to make a string a palindrome.
+// Runs in O(N) time and O(N) extra space for favorLeft and favorRight.
+func MakePalindrome(str string) string {
+	letters := []rune(str)
+	favorLeft := make([]rune, len(letters))
+	copy(favorLeft, letters)
+	favorRight := make([]rune, len(letters))
+	copy(favorRight, letters)
+	left, right := 0, len(favorLeft)-1
+	for left < right {
+		if favorLeft[left] != favorLeft[right] {
+			// insert the left character on the right side
+			favorLeft = append(favorLeft, 'x')
+			copy(favorLeft[right+2:], favorLeft[right+1:])
+			favorLeft[right+1] = favorLeft[left]
+			right++
+		}
+		left++
+		right--
+	}
+	left, right = 0, len(favorRight)-1
+	for left < right {
+		if favorRight[left] != favorRight[right] {
+			// insert the right character on the left side
+			favorRight = append(favorRight, 'x')
+			copy(favorRight[left+1:], favorRight[left:])
+			favorRight[left] = favorRight[right+1]
+			right++
+		}
+		left++
+		right--
+	}
+	return chooseResult(favorLeft, favorRight)
+}
+
+func chooseResult(left, right []rune) string {
+	if len(left) < len(right) {
+		return string(left)
+	} else if len(left) == len(right) {
+		if left[0] < right[0] {
+			return string(left)
+		}
+		return string(right)
+	} else {
+		return string(right)
+	}
+}


Test patch:
diff --git a/day34/problem_test.go b/day34/problem_test.go
new file mode 100644
index 0000000..1f1fd60
--- /dev/null
+++ b/day34/problem_test.go
@@ -0,0 +1,30 @@
+package day34
+
+import "testing"
+
+var testcases = []struct {
+	input, expected string
+}{
+	{"race", "ecarace"},
+	{"google", "elgoogle"},
+	{"add", "adda"},
+	{"caoobac", "caboobac"},
+	{"abc", "abcba"},
+}
+
+func TestMakePalindrome(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MakePalindrome(tc.input); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMakePalindrome(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MakePalindrome(tc.input)
+		}
+	}
+}