ā† Back to DevBytes
Go August 05, 2026 8 min read

Solving Count and Say in Go: Step-by-Step Guide

Introduction to the Count and Say Problem

The Count and Say sequence is one of those classic algorithmic puzzles that appears in coding interviews and competitive programming platforms like LeetCode. At first glance, it looks deceptively simple, but it requires careful string manipulation and a solid understanding of iterative processing. In this tutorial, we'll walk through solving the Count and Say problem in Go, breaking down the logic step by step.

What Is the Count and Say Sequence?

The Count and Say sequence is a sequence of digit strings defined by a recursive formula:

To generate the next term, you "read" the previous term aloud, counting the number of digits in groups of the same digit. For example, if the current term is "1211", you would say "one 1, one 2, two 1s", which produces the next term "111221".

Here are the first several terms of the sequence:

Why It Matters

While the Count and Say problem may seem like a purely academic exercise, it actually tests several important programming skills:

Mastering this problem builds a foundation for more complex string and sequence-based challenges.

Understanding the Algorithm

Before writing any code, let's understand the algorithm conceptually. Given an integer n, we need to produce the nth term of the Count and Say sequence. We start with the base case "1" and iteratively apply the run-length encoding process n - 1 times.

The Run-Length Encoding Step

The core operation is transforming one term into the next. Here's the process:

For example, transforming "1211":

Implementing the Solution in Go

Now let's translate this algorithm into Go code. Go's standard library provides excellent string handling capabilities through the strings package, and its straightforward syntax makes this implementation clean and readable.

Basic Implementation

Here is a complete, working implementation of the Count and Say problem in Go:

package main

import (
	"fmt"
	"strconv"
)

func countAndSay(n int) string {
	if n <= 0 {
		return ""
	}

	// Base case
	result := "1"

	// Generate terms 2 through n
	for i := 2; i <= n; i++ {
		result = nextTerm(result)
	}

	return result
}

func nextTerm(s string) string {
	var builder []byte
	count := 1

	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			count++
		} else {
			builder = append(builder, []byte(strconv.Itoa(count))...)
			builder = append(builder, s[i-1])
			count = 1
		}
	}

	// Append the last group
	builder = append(builder, []byte(strconv.Itoa(count))...)
	builder = append(builder, s[len(s)-1])

	return string(builder)
}

func main() {
	for i := 1; i <= 10; i++ {
		fmt.Printf("Term %d: %s\n", i, countAndSay(i))
	}
}

Let's break down this implementation:

Using strings.Builder for Better Performance

Go 1.10 introduced the strings.Builder type, which is specifically designed for efficient string concatenation. Let's rewrite the nextTerm function to use it:

package main

import (
	"fmt"
	"strconv"
	"strings"
)

func countAndSay(n int) string {
	if n <= 0 {
		return ""
	}

	result := "1"
	for i := 2; i <= n; i++ {
		result = nextTerm(result)
	}
	return result
}

func nextTerm(s string) string {
	var sb strings.Builder
	count := 1

	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			count++
		} else {
			sb.WriteString(strconv.Itoa(count))
			sb.WriteByte(s[i-1])
			count = 1
		}
	}

	sb.WriteString(strconv.Itoa(count))
	sb.WriteByte(s[len(s)-1])

	return sb.String()
}

func main() {
	fmt.Println(countAndSay(1))  // Output: 1
	fmt.Println(countAndSay(4))  // Output: 1211
	fmt.Println(countAndSay(5))  // Output: 111221
}

The strings.Builder approach is preferred because it minimizes memory allocations. Each call to WriteString or WriteByte appends to an internal buffer, and the final String() call produces the result without unnecessary copies.

Optimizing the Implementation

Avoiding strconv.Itoa Overhead

In the Count and Say sequence, the count of consecutive digits never exceeds 3 for the first 30 terms. This is a mathematical property of the sequence ā€” it never contains a digit greater than 3, and no run of identical digits is longer than 3. We can exploit this by converting the count to a character directly:

func nextTerm(s string) string {
	var sb strings.Builder
	count := 1

	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			count++
		} else {
			sb.WriteByte(byte('0' + count))
			sb.WriteByte(s[i-1])
			count = 1
		}
	}

	sb.WriteByte(byte('0' + count))
	sb.WriteByte(s[len(s)-1])

	return sb.String()
}

This eliminates the strconv.Itoa call entirely, which removes a function call and its associated overhead. While the performance difference is small for low values of n, it becomes noticeable when generating many terms.

Preallocating the Builder Capacity

Another optimization is to preallocate the builder's internal buffer. Since each term is roughly 1.3 times the length of the previous term, we can estimate the needed capacity:

func nextTerm(s string) string {
	var sb strings.Builder
	sb.Grow(len(s) * 4 / 3)

	count := 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			count++
		} else {
			sb.WriteByte(byte('0' + count))
			sb.WriteByte(s[i-1])
			count = 1
		}
	}

	sb.WriteByte(byte('0' + count))
	sb.WriteByte(s[len(s)-1])

	return sb.String()
}

The Grow method ensures the internal buffer has enough space, reducing the number of reallocations as the string grows.

Testing and Validation

A robust solution needs thorough testing. Go's built-in testing framework makes this straightforward. Here's a complete test file:

package main

import "testing"

func TestCountAndSay(t *testing.T) {
	tests := []struct {
		n        int
		expected string
	}{
		{0, ""},
		{1, "1"},
		{2, "11"},
		{3, "21"},
		{4, "1211"},
		{5, "111221"},
		{6, "312211"},
		{7, "13112221"},
		{8, "1113213211"},
		{9, "31131211131221"},
		{10, "13211311123113112211"},
	}

	for _, tt := range tests {
		result := countAndSay(tt.n)
		if result != tt.expected {
			t.Errorf("countAndSay(%d) = %q, expected %q", tt.n, result, tt.expected)
		}
	}
}

func TestCountAndSayNegative(t *testing.T) {
	result := countAndSay(-5)
	if result != "" {
		t.Errorf("countAndSay(-5) = %q, expected empty string", result)
	}
}

func BenchmarkCountAndSay(b *testing.B) {
	for i := 0; i < b.N; i++ {
		countAndSay(30)
	}
}

Run the tests with go test -v and the benchmark with go test -bench=.. The benchmark helps you measure the impact of the optimizations discussed earlier.

Best Practices

Handle Edge Cases Explicitly

Always validate input. The function should handle n <= 0 gracefully by returning an empty string or an error, depending on your API contract. Document this behavior clearly.

Use strings.Builder for String Construction

Never concatenate strings with the + operator inside a loop. Each concatenation creates a new string and copies all previous content, leading to O(nĀ²) complexity. Always use strings.Builder for iterative string construction.

Separate Concerns

Keep the run-length encoding logic in a separate function (nextTerm) rather than inlining it. This makes the code easier to test, debug, and reuse. If you later need run-length encoding for another problem, you can extract it into its own package.

Write Table-Driven Tests

Go's testing framework excels at table-driven tests. Define your test cases as a slice of structs, then iterate over them. This pattern makes it easy to add new cases and identify which specific input fails.

Consider Memory Limits for Large n

The Count and Say sequence grows exponentially. By term 30, the string is over 5,000 characters long. By term 40, it exceeds 100,000 characters. For very large values of n, consider whether you need the full string or just its length, and be mindful of memory consumption.

Common Pitfalls

Conclusion

The Count and Say problem is an excellent exercise in string manipulation, iterative algorithms, and run-length encoding. By breaking the problem into a base case and a single transformation step, you can build a clean and efficient solution in Go. Using strings.Builder for string construction, handling edge cases explicitly, and writing table-driven tests ensure your implementation is both performant and maintainable. Whether you're preparing for a coding interview or simply sharpening your Go skills, mastering this problem gives you tools that transfer directly to real-world string processing and compression tasks.

ā€” Ad ā€”

Google AdSense will appear here after approval

ā† Back to all articles