Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 86
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a string of parentheses, write a function to compute the minimum number of parentheses to be removed to make the string valid (i.e. each open parenthesis is eventually closed).

For example, given the string `"()())()"`, you should return 1. Given the string `")("`, you should return 2, since we must remove all of them.

Pull request description:
Day86
Resolves #181.

Patch:
diff --git a/README.md b/README.md
index 0d6f718..f3cf2c1 100644
--- a/README.md
+++ b/README.md
@@ -95,3 +95,4 @@ problems from
 * [Day 83](https://github.com/vaskoz/dailycodingproblem-go/issues/175)
 * [Day 84](https://github.com/vaskoz/dailycodingproblem-go/issues/177)
 * [Day 85](https://github.com/vaskoz/dailycodingproblem-go/issues/179)
+* [Day 86](https://github.com/vaskoz/dailycodingproblem-go/issues/181)
diff --git a/day86/problem.go b/day86/problem.go
new file mode 100644
index 0000000..5550781
--- /dev/null
+++ b/day86/problem.go
@@ -0,0 +1,21 @@
+package day86
+
+// MinRemovedParens calculates the minimum of parentheses to remove to make
+// a list of them valid. Each open must have a corresponding close.
+// Runs in O(N) time with O(1) space.
+func MinRemovedParens(parens string) int {
+	opens := 0
+	count := 0
+	for _, r := range parens {
+		if r == '(' {
+			opens++
+		} else if r == ')' {
+			if opens == 0 {
+				count++
+			} else {
+				opens--
+			}
+		}
+	}
+	return count + opens
+}


Test patch:
diff --git a/day86/problem_test.go b/day86/problem_test.go
new file mode 100644
index 0000000..d5068dc
--- /dev/null
+++ b/day86/problem_test.go
@@ -0,0 +1,31 @@
+package day86
+
+import "testing"
+
+var testcases = []struct {
+	input    string
+	expected int
+}{
+	{"()())()", 1},
+	{")(", 2},
+	{"((()(())))", 0},
+	{"(((()(())))", 1},
+	{"((()(()))))", 1},
+}
+
+func TestMinRemovedParens(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MinRemovedParens(tc.input); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMinRemovedParens(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinRemovedParens(tc.input)
+		}
+	}
+}