LeetCode Problem 38

Difficulty: 🟡 Medium
Topics: String

Solution

LeetCode 38, Count and Say

Problem Understanding

The problem asks us to generate the nth term of the "count-and-say" sequence. This sequence is built recursively, where each term is created by describing the previous term.

The sequence starts with:

1

To generate the next term, we read the current string from left to right and describe groups of consecutive identical digits.

For example:

"1"

contains one 1, so the next term becomes:

"11"

Then:

"11"

contains two 1s, so the next term becomes:

"21"

Then:

"21"

contains one 2 followed by one 1, so the next term becomes:

"1211"

The input n represents which term in the sequence we need to return. The output is the exact string corresponding to that term.

The constraints are small:

1 <= n <= 30

This tells us several important things:

• We never need to generate extremely large sequences.
• Exponential explosion is somewhat limited because n is capped at 30.
• A direct iterative simulation is practical.
• We should focus more on clean sequence generation than on advanced optimization techniques.

An important detail is that the sequence is generated from consecutive groups only. For example:

"111221"

must be interpreted as:

• three 1s
• two 2s
• one 1

which becomes:

"312211"

A naive implementation can fail if it does not correctly handle transitions between groups or if it forgets to process the final group after finishing the loop.

The key edge cases include:

• n = 1, which should immediately return "1"
• Strings where every character is different
• Strings where all characters are identical
• Correctly processing the last run of digits after iteration ends

The problem guarantees that n is always valid and positive, so we do not need additional input validation.

Approaches

Brute Force Approach

The brute force approach is to recursively generate every previous term until we reach the nth term.

For each term:

1. Scan the previous string from left to right.
2. Count consecutive repeated characters.
3. Append "count + digit" to build the next string.
4. Repeat until term n is generated.

This approach is correct because every term is defined directly from the previous one. If we accurately perform run-length encoding at every step, we will eventually obtain the correct sequence.

However, recursion introduces unnecessary overhead. Since every term depends only on the immediately previous term, storing deep recursive call stacks is not ideal. The recursive approach also risks reduced readability and slightly higher memory usage.

Optimal Approach

The optimal solution uses an iterative simulation.

The key observation is that each term depends only on the previous term, not on the entire history of the sequence.

This means we can:

• Start from "1"
• Repeatedly generate the next string
• Replace the current string each iteration

To generate the next term efficiently:

• Use a pointer to scan the string
• Count consecutive identical digits
• Append the count and digit to a result builder
• Continue until the entire string is processed

This approach is efficient, straightforward, and avoids recursion overhead.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(T)	O(T)	Recursive generation of all terms, extra recursion stack
Optimal	O(T)	O(T)	Iterative run-length encoding generation

Here, T represents the total number of characters generated across all sequence terms up to n.

Algorithm Walkthrough

1. Initialize the sequence with the base case "1".

This is the first term of the sequence, and every later term is derived from it. 2. Repeat the generation process n - 1 times.

Since we already have the first term, we only need to generate the remaining terms. 3. For each iteration, create an empty list or string builder to construct the next sequence.

Building strings incrementally using concatenation is inefficient in many languages, so using a builder structure is preferable. 4. Scan the current string from left to right.

Use an index pointer to track the current position. 5. Count consecutive identical characters.

Start a counter at 1, then continue advancing while the next character matches the current one. 6. Append the count followed by the digit to the builder.

For example:

• "111" becomes "31"
• "22" becomes "22"

7. Continue scanning until the entire string is processed.

Every character must belong to exactly one consecutive group. 8. Replace the current sequence with the newly constructed string.

This newly generated string becomes the input for the next iteration. 9. After completing all iterations, return the final sequence.

Why it works

The algorithm works because every term in the sequence is defined as the run-length encoding of the previous term. During each iteration, the algorithm partitions the current string into maximal groups of identical consecutive digits. Each group is encoded exactly once as "count + digit". Since every character belongs to one and only one group, the generated string precisely matches the problem definition.

Python Solution

class Solution:
    def countAndSay(self, n: int) -> str:
        current = "1"

        for _ in range(n - 1):
            next_sequence = []
            index = 0

            while index < len(current):
                count = 1

                while (
                    index + 1 < len(current)
                    and current[index] == current[index + 1]
                ):
                    count += 1
                    index += 1

                next_sequence.append(str(count))
                next_sequence.append(current[index])

                index += 1

            current = "".join(next_sequence)

        return current

The implementation begins with the base sequence "1".

The outer loop runs n - 1 times because the first term already exists. During each iteration, we construct the next term from the current one.

The variable index scans through the current string. For each position, we count how many consecutive identical digits appear.

The inner while loop advances as long as the next character matches the current one. This correctly groups repeated digits together.

After counting a group, we append:

• the frequency
• the digit itself

to the next_sequence list.

Using a list and "".join() is efficient because repeated string concatenation would create many intermediate strings.

Finally, the newly generated sequence replaces current, and the process repeats until the desired term is produced.

Go Solution

import (
	"strconv"
	"strings"
)

func countAndSay(n int) string {
	current := "1"

	for i := 0; i < n-1; i++ {
		var builder strings.Builder

		index := 0

		for index < len(current) {
			count := 1

			for index+1 < len(current) &&
				current[index] == current[index+1] {
				count++
				index++
			}

			builder.WriteString(strconv.Itoa(count))
			builder.WriteByte(current[index])

			index++
		}

		current = builder.String()
	}

	return current
}

The Go implementation follows the same algorithmic structure as the Python version.

Instead of using a list for string construction, Go uses strings.Builder, which is efficient for repeated string appends.

strconv.Itoa() converts the integer count into a string before appending it.

Since Go strings are byte indexed and the sequence contains only digits, accessing characters with current[index] is safe and efficient.

There are no concerns about integer overflow because the sequence lengths remain relatively small within the problem constraints.

Worked Examples

Example 1

Input:

n = 4

Initial sequence:

"1"

Iteration 1

Current:

"1"

Group	Count	Append
"1"	1	"11"

Next sequence:

"11"

Iteration 2

Current:

"11"

Group	Count	Append
"11"	2	"21"

Next sequence:

"21"

Iteration 3

Current:

"21"

Group	Count	Append
"2"	1	"12"
"1"	1	"11"

Next sequence:

"1211"

Final answer:

"1211"

Example 2

Input:

n = 1

Initial sequence:

"1"

No iterations are needed because the first term is already the answer.

Final answer:

"1"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(T)	Every generated character is scanned once
Space	O(T)	Storage for the generated sequence

The algorithm processes each generated sequence exactly once. If T is the total number of characters across all generated terms up to n, then the total runtime is proportional to T.

The space complexity is also O(T) because we store the current sequence and construct the next one during each iteration.

Although the sequence length grows over time, the constraint n <= 30 keeps the total size manageable.

Test Cases

sol = Solution()

assert sol.countAndSay(1) == "1"          # Base case
assert sol.countAndSay(2) == "11"         # One digit repeated once
assert sol.countAndSay(3) == "21"         # Two identical digits
assert sol.countAndSay(4) == "1211"       # Standard example
assert sol.countAndSay(5) == "111221"     # Multiple groups
assert sol.countAndSay(6) == "312211"     # Larger sequence
assert sol.countAndSay(7) == "13112221"   # Mixed group sizes
assert sol.countAndSay(8) == "1113213211" # Longer generated string
assert sol.countAndSay(10) == "13211311123113112211"  # Stress moderate growth

Test	Why
n = 1	Validates base case handling
n = 2	Tests simplest transformation
n = 3	Tests counting repeated digits
n = 4	Confirms official example
n = 5	Tests multiple consecutive groups
n = 6	Validates larger transitions
n = 7	Tests alternating group sizes
n = 8	Confirms continued iterative correctness
n = 10	Stress test for longer sequences

Edge Cases

One important edge case is n = 1. This is the base case of the entire sequence. A common bug is running the generation loop even when no additional terms should be created. The implementation handles this correctly because the loop executes n - 1 times, which becomes zero iterations when n = 1.

Another important edge case occurs when all digits in the current string are identical. For example:

"1111"

A buggy implementation might accidentally split the run into multiple groups or fail to count all repetitions. The inner loop in the solution continues advancing until the digit changes, guaranteeing that the entire run is counted together.

A third important edge case involves processing the final group in the string. Many implementations correctly detect transitions between groups but forget to append the last group after the loop ends. This solution avoids that issue because every group is processed immediately during traversal, including the final one.

Another subtle case occurs when every digit differs from the next one, such as:

"121212"

In this scenario, every group has length one. The algorithm still works correctly because the count starts at 1 before checking for repeated digits.