Count and Say - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Count and Say" Problem in Go

Difficulty: Medium | Tags: String

Introduction

The "Count and Say" problem involves generating a sequence where each term is derived from the previous term by describing its digits. This problem tests string manipulation and recursion or iteration skills.

Problem Analysis

The sequence starts with "1", and each subsequent term is generated by reading the previous term's digits and counting consecutive occurrences. For example, the third term is "21" because the second term "11" is read as "two 1s".

Solution Approach

The solution involves iteratively generating each term from the previous one. For each term, we traverse the string, count consecutive identical digits, and append the count followed by the digit to the result string.

Go Implementation


func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    prev := countAndSay(n - 1)
    var result strings.Builder
    count := 1
    for i := 1; i < len(prev); i++ {
        if prev[i] == prev[i-1] {
            count++
        } else {
            result.WriteString(strconv.Itoa(count))
            result.WriteByte(prev[i-1])
            count = 1
        }
    }
    result.WriteString(strconv.Itoa(count))
    result.WriteByte(prev[len(prev)-1])
    return result.String()
}

Complexity Analysis

The time complexity is O(2^n) in the worst case, as each term can be up to twice the length of the previous term. The space complexity is O(2^n) due to the recursive call stack and string storage.

Testing and Examples

Test cases include:
- n = 1 → "1"
- n = 4 → "1211"
- n = 5 → "111221"
Edge cases involve n = 1 (base case) and n = 30 (maximum constraint).

Best Practices and Tips

Use a strings.Builder for efficient string concatenation. For larger n, consider an iterative approach to avoid stack overflow. Break down the problem into smaller steps: counting digits and building the next term.

Read more