Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 199
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a string of parentheses, find the balanced string that can be produced from it using the minimum number of insertions and deletions. If there are multiple solutions, return any of them.

For example, given `"(()"`, you could return `"(())"`. Given `"))()("`, you could return `"()()()()"`.

Pull request description:
Day199
Resolves #409.

Patch:
diff --git a/README.md b/README.md
index 5ceabd7..ff4f882 100644
--- a/README.md
+++ b/README.md
@@ -207,3 +207,4 @@ problems from
 * [Day 195](https://github.com/vaskoz/dailycodingproblem-go/issues/401)
 * [Day 196](https://github.com/vaskoz/dailycodingproblem-go/issues/404)
 * [Day 197](https://github.com/vaskoz/dailycodingproblem-go/issues/405)
+* [Day 199](https://github.com/vaskoz/dailycodingproblem-go/issues/409)
diff --git a/day199/problem.go b/day199/problem.go
new file mode 100644
index 0000000..d63a869
--- /dev/null
+++ b/day199/problem.go
@@ -0,0 +1,25 @@
+package day199
+
+import "strings"
+
+// BalanceParens balances unbalanced parens.
+// Runs in O(N) time and O(N) extra space.
+// Only accepts a string composed of '(' and ')'.
+func BalanceParens(parens string) string {
+	var sb strings.Builder
+	opens := 0
+	for _, r := range parens {
+		if r == '(' {
+			opens++
+		} else if r == ')' && opens == 0 {
+			sb.WriteRune('(')
+		} else {
+			opens--
+		}
+		sb.WriteRune(r)
+	}
+	for i := 0; i < opens; i++ {
+		sb.WriteRune(')')
+	}
+	return sb.String()
+}


Test patch:
diff --git a/day199/problem_test.go b/day199/problem_test.go
new file mode 100644
index 0000000..b78a3f1
--- /dev/null
+++ b/day199/problem_test.go
@@ -0,0 +1,29 @@
+package day199
+
+import "testing"
+
+var testcases = []struct {
+	parens   string
+	expected string
+}{
+	{"(()", "(())"},
+	{"))()(", "()()()()"},
+	{"))(", "()()()"},
+}
+
+func TestBalanceParens(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := BalanceParens(tc.parens); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkBalanceParens(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BalanceParens(tc.parens)
+		}
+	}
+}