Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 231
Good morning! Here's your coding interview problem for today.

This problem was asked by IBM.

Given a string with repeated characters, rearrange the string so that no two adjacent characters are the same. If this is not possible, return None.

For example, given "aaabbc", you could return "ababac". Given "aaab", return None.

Pull request description:
Day231
Resolves #475.

Patch:
diff --git a/README.md b/README.md
index c8f04d7..ac0ab80 100644
--- a/README.md
+++ b/README.md
@@ -239,3 +239,4 @@ problems from
 * [Day 226](https://github.com/vaskoz/dailycodingproblem-go/issues/467)
 * [Day 228](https://github.com/vaskoz/dailycodingproblem-go/issues/470)
 * [Day 230](https://github.com/vaskoz/dailycodingproblem-go/issues/473)
+* [Day 231](https://github.com/vaskoz/dailycodingproblem-go/issues/475)
diff --git a/day231/problem.go b/day231/problem.go
new file mode 100644
index 0000000..054e587
--- /dev/null
+++ b/day231/problem.go
@@ -0,0 +1,41 @@
+package day231
+
+import (
+	"sort"
+	"strings"
+)
+
+// NoAdjacent returns a rearranged string
+// where no adjacent characters are the same.
+// Runs in O(N log N) due to sorting runes by frequency.
+func NoAdjacent(s string) string {
+	freq := make(map[rune]int)
+	for _, r := range s {
+		freq[r]++
+	}
+	type frequency struct {
+		r     rune
+		count int
+	}
+	letters := make([]*frequency, 0, len(freq))
+	for letter, count := range freq {
+		letters = append(letters, &frequency{letter, count})
+	}
+	sort.Slice(letters, func(i, j int) bool {
+		return letters[i].count > letters[j].count
+	})
+	var sb strings.Builder
+	for len(letters) != 0 {
+		if len(letters) == 1 && letters[0].count > 1 {
+			return ""
+		}
+		for _, f := range letters {
+			sb.WriteRune(f.r)
+			f.count--
+		}
+		for len(letters) != 0 && letters[len(letters)-1].count == 0 {
+			letters = letters[:len(letters)-1]
+		}
+	}
+	return sb.String()
+}


Test patch:
diff --git a/day231/problem_test.go b/day231/problem_test.go
new file mode 100644
index 0000000..4a7f15b
--- /dev/null
+++ b/day231/problem_test.go
@@ -0,0 +1,28 @@
+package day231
+
+import "testing"
+
+var testcases = []struct {
+	s, expected string
+}{
+	{"bbbaa", "babab"},
+	{"aaabbc", "abcaba"},
+	{"aaab", ""},
+}
+
+func TestNoAdjacent(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := NoAdjacent(tc.s); result != tc.expected {
+			t.Errorf("Expected %s, got %s", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkNoAdjacent(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			NoAdjacent(tc.s)
+		}
+	}
+}