38. Count and Say - Solution & Explanation

Q: Is Count and Say easy or hard?

Count and Say is typically rated Medium because the logic requires careful grouping of consecutive characters while building new strings. The algorithm itself is straightforward, but off‑by‑one errors and incorrect group handling can make the implementation tricky.

Q: Count and Say Python/Java solution

In Python or Java, iterate through the current string and count consecutive characters. When the character changes, append the count and the digit to a result string or StringBuilder. Repeat this process n-1 times starting from "1" to generate the nth term.

Q: How to solve Count and Say in O(n)?

Strict O(n) time is not achievable because the output string grows with each iteration. The optimal approach is O(n * L), where you iterate n times and process the current string in a single pass. Each pass counts consecutive characters and appends count and digit pairs.

Q: What is the best approach for Count and Say?

The iterative string simulation approach is the most practical solution. Start with "1" and repeatedly scan the current string to count consecutive digits, appending count and digit to form the next term. This runs in O(n * L) time where L is the length of the generated string and uses O(L) space.

Q: Is Count and Say asked at Google/Amazon/Meta?

Count and Say appears in interview practice sets for companies like Amazon, Google, and Microsoft, though it is more commonly used as a warm‑up string problem. It tests the ability to simulate processes, handle consecutive groups, and manipulate strings efficiently.

Q: What data structure is used in Count and Say?

The solution mainly uses string processing with counters. A loop scans the string while tracking the current character and its frequency, then appends the result to a new string or string builder. No complex data structures like hash maps or trees are required.

Q: What is the time complexity of Count and Say?

Time complexity is O(n * L), where n is the requested term and L is the length of the final string. Each iteration scans the current string once to group consecutive digits and build the next string. Space complexity is O(L) for storing the generated term.

The problem

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"
countAndSay(n) is the run-length encoding of countAndSay(n - 1).

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511".

Given a positive integer n, return the n^th element of the count-and-say sequence.

Example 1:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

Example 2:

Input: n = 1

Output: "1"

Explanation:

This is the base case.

Constraints:

1 <= n <= 30

Follow up: Could you solve it iteratively?

Approach overview

Problem Overview: Generate the nth term of the Count and Say sequence. Each term is created by reading the previous term and describing consecutive digits ("one 1", "two 1s", etc.), producing the next string.

Approach 1: Iterative String Simulation (O(n * L) time, O(L) space)

Build the sequence step by step starting from "1". For every iteration, scan the current string and group consecutive identical digits. Count how many times a digit repeats, append count + digit to a new string, then continue scanning. The key operation is a linear pass with two pointers (or an index and counter) to detect runs of the same character. If the length of the nth term is L, the total work is O(n * L) time with O(L) space for the constructed string.

This method is essentially string simulation. No advanced data structures are required—just careful iteration and string building. Problems involving sequence generation like this often fall under string manipulation and simulation. Iterative construction avoids recursion overhead and is straightforward to debug.

Approach 2: Recursive Construction (O(n * L) time, O(n + L) space)

Define the problem recursively: the nth term depends entirely on the (n-1)th term. First compute countAndSay(n-1), then run the same grouping logic over that returned string to build the nth result. The recursion depth is n, and each level processes a string of length L, so the time complexity remains O(n * L). Additional space comes from the call stack (O(n)) plus the generated string (O(L)).

This approach expresses the mathematical definition of the sequence directly. It pairs naturally with problems that involve repeated transformations of previous results, a pattern commonly discussed in recursion. The tradeoff is extra stack usage and slightly more overhead than the iterative loop.

Recommended for interviews: The iterative approach is typically expected. It shows you can simulate the process efficiently using a single pass through the string. Mentioning the recursive formulation demonstrates understanding of the sequence definition, but the iterative solution signals stronger control over space usage and implementation details.

Approach 1: Iterative Approach

This approach involves constructing the sequence iteratively. We start from the base case, which is '1', and iteratively build up the strings by counting and saying the digits from the last constructed string.

Python

def countAndSay(n: int) -> str:
    result = '1'
    for _ in range(n - 1):
        current_result = ''
        i = 0
        while i < len(result):
            count = 1
            while i + 1 < len(result) and result[i] == result[i + 1]:
                i += 1
                count += 1
            current_result += str(count) + result[i]
            i += 1
        result = current_result
    return result

if __name__ == "__main__":
    print(countAndSay(4))

Java

public class Solution {
    public String countAndSay(int n) {
        String result = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder temp = new StringBuilder();
            for (int j = 0; j < result.length(); ) {
                char current_digit = result.charAt(j);
                int count = 0;
                while (j < result.length() && result.charAt(j) == current_digit) {
                    count++;
                    j++;
                }
                temp.append(count).append(current_digit);
            }
            result = temp.toString();
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countAndSay(4));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

string countAndSay(int n) {
    string result = "1";
    for (int i = 1; i < n; i++) {
        string temp = "";
        for (int j = 0; j < result.length(); ) {
            char current_digit = result[j];
            int count = 0;
            while (j < result.length() && result[j] == current_digit) {
                count++;
                j++;
            }
            temp += to_string(count) + current_digit;
        }
        result = temp;
    }
    return result;
}

int main() {
    cout << countAndSay(4) << endl;
    return 0;
}

JavaScript

function countAndSay(n) {
    let result = "1";

    for (let i = 1; i < n; i++) {
        let current = "";
        for (let j = 0; j < result.length; ) {
            let count = 0;
            const currentChar = result[j];
            while (j < result.length && result[j] === currentChar) {
                j++;
                count++;
            }
            current += `${count}${currentChar}`;
        }
        result = current;
    }

    return result;
}

console.log(countAndSay(4));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* countAndSay(int n) {
    char* result = malloc(2);
    strcpy(result, "1");
    for (int i = 1; i < n; i++) {
        int len = strlen(result);
        char* temp = malloc(2 * len + 1);
        int index = 0;
        for (int j = 0; j < len;) {
            char current_digit = result[j];
            int count = 0;
            while (j < len && result[j] == current_digit) {
                count++;
                j++;
            }
            index += sprintf(temp + index, "%d%c", count, current_digit);
        }
        free(result);
        result = temp;
    }
    return result;
}

int main() {
    int n = 4;
    char* result = countAndSay(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

using System;
using System.Text;

public class Solution {
    public string CountAndSay(int n) {
        string result = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder temp = new StringBuilder();
            int j = 0;
            while (j < result.Length) {
                char currentDigit = result[j];
                int count = 0;
                while (j < result.Length && result[j] == currentDigit) {
                    j++;
                    count++;
                }
                temp.Append(count).Append(currentDigit);
            }
            result = temp.ToString();
        }
        return result;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountAndSay(4));
    }
}

Python's solution leverages concise string concatenation along with iteration to accumulate the count and the said digits for producing the next line in the sequence.

Complexity

Time Complexity: O(2^n).
Space Complexity: O(2^n).

Try this approach in the editor

Approach 2: Recursive Approach

The recursive approach defines the function countAndSay recursively by computing countAndSay(n-1), then generating the count-and-say encoding for it.

This method involves less memory usage on the function stack compared to an iterative approach but still leverages recursion for elegance.

Python

def next_sequence(seq: str) -> str:
    result = ''
    i = 0
    while i < len(seq):
        count = 1
        while i + 1 < len(seq) and seq[i] == seq[i + 1]:
            i += 1
            count += 1
        result += str(count) + seq[i]
        i += 1
    return result


def count_and_say(n: int) -> str:
    if n == 1:
        return '1'
    return next_sequence(count_and_say(n - 1))


if __name__ == "__main__":
    print(count_and_say(4))

Java

public class Solution {
    private String nextSequence(String seq) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < seq.length();) {
            int count = 0;
            char currentChar = seq.charAt(i);
            while (i < seq.length() && seq.charAt(i) == currentChar) {
                i++;
                count++;
            }
            result.append(count).append(currentChar);
        }
        return result.toString();
    }

    public String countAndSay(int n) {
        if (n == 1) return "1";
        String prevResult = countAndSay(n - 1);
        return nextSequence(prevResult);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countAndSay(4));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

string nextSequence(const string& seq) {
    string result = "";
    for (int i = 0; i < seq.length(); ) {
        char current_digit = seq[i];
        int count = 0;
        while (i < seq.length() && seq[i] == current_digit) {
            count++;
            i++;
        }
        result += to_string(count) + current_digit;
    }
    return result;
}

string countAndSay(int n) {
    if (n == 1) return "1";
    string prev_result = countAndSay(n - 1);
    return nextSequence(prev_result);
}

int main() {
    cout << countAndSay(4) << endl;
    return 0;
}

JavaScript

function nextSequence(seq) {
    let result = "";
    let i = 0;
    while (i < seq.length) {
        let count = 0;
        const currentChar = seq[i];
        while (i < seq.length && seq[i] === currentChar) {
            i++;
            count++;
        }
        result += `${count}${currentChar}`;
    }
    return result;
}

function countAndSay(n) {
    if (n === 1) return "1";
    return nextSequence(countAndSay(n - 1));
}

console.log(countAndSay(4));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* nextSequence(const char* seq) {
    size_t len = strlen(seq);
    char* result = malloc((2 * len + 1) * sizeof(char));
    int index = 0;
    for (int i = 0; i < len;) {
        char current_char = seq[i];
        int count = 0;
        while (i < len && seq[i] == current_char) {
            count++;
            i++;
        }
        index += sprintf(result + index, "%d%c", count, current_char);
    }
    return result;
}

char* countAndSay(int n) {
    if (n == 1) return strdup("1");
    char* prev_result = countAndSay(n - 1);
    char* result = nextSequence(prev_result);
    free(prev_result);
    return result;
}

int main() {
    char* result = countAndSay(4);
    printf("%s\n", result);
    free(result);
    return 0;
}

using System;
using System.Text;

public class Solution {
    private string NextSequence(string seq) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < seq.Length;) {
            char currentChar = seq[i];
            int count = 0;
            while (i < seq.Length && seq[i] == currentChar) {
                i++;
                count++;
            }
            result.Append(count).Append(currentChar);
        }
        return result.ToString();
    }

    public string CountAndSay(int n) {
        if (n == 1) return "1";
        string prevResult = CountAndSay(n - 1);
        return NextSequence(prevResult);
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountAndSay(4));
    }
}

Python's recursive approach utilizes next_sequence to derive each pattern step-by-step recursively until reaching the required iteration, reducing overall complexity with easy-to-read recursive logic.

Complexity

Time Complexity: O(2^n).
Space Complexity: O(2^n) for sequence storage, O(n) recursion stack.

Try this approach in the editor

Approach 3: Simulation

The task requires outputting the appearance sequence of the n-th item, where the n-th item is the description of the n-1-th item in the sequence. Therefore, we iterate n-1 times. In each iteration, we use fast and slow pointers, denoted as j and i respectively, to record the current character's position and the position of the next character that is not equal to the current character. We then update the sequence of the previous item to be j-i occurrences of the current character.

Time Complexity:

The outer loop runs n - 1 times, iterating to generate the "Count and Say" sequence up to the nth term.
The inner while loop iterates through each character in the current string s and counts the consecutive occurrences of the same character.
The inner while loop runs in O(m) time, where m is the length of the current string s.

Overall, the time complexity is O(n times m), where n is the input parameter representing the term to generate, and m is the maximum length of the string in the sequence.

Space Complexity: O(m).

TypeScript

function countAndSay(n: number): string {
    let s = '1';
    for (let i = 1; i < n; i++) {
        let t = '';
        let cur = s[0];
        let count = 1;
        for (let j = 1; j < s.length; j++) {
            if (s[j] !== cur) {
                t += `${count}${cur}`;
                cur = s[j];
                count = 0;
            }
            count++;
        }
        t += `${count}${cur}`;
        s = t;
    }
    return s;
}

func countAndSay(n int) string {
	s := "1"
	for k := 0; k < n-1; k++ {
		t := &strings.Builder{}
		i := 0
		for i < len(s) {
			j := i
			for j < len(s) && s[j] == s[i] {
				j++
			}
			t.WriteString(strconv.Itoa(j - i))
			t.WriteByte(s[i])
			i = j
		}
		s = t.String()
	}
	return s
}

Rust

use std::iter::once;

impl Solution {
    pub fn count_and_say(n: i32) -> String {
        (1..n)
            .fold(vec![1], |curr, _| {
                let mut next = vec![];
                let mut slow = 0;
                for fast in 0..=curr.len() {
                    if fast == curr.len() || curr[slow] != curr[fast] {
                        next.extend(once((fast - slow) as u8).chain(once(curr[slow])));
                        slow = fast;
                    }
                }
                next
            })
            .into_iter()
            .map(|digit| (digit + b'0') as char)
            .collect()
    }
}

PHP

class Solution {
    /**
     * @param integer $n
     * @return string
     */

    function countAndSay($n) {
        if ($n <= 0) {
            return '';
        }

        $result = '1';
        for ($i = 2; $i <= $n; $i++) {
            $count = 1;
            $say = '';
            for ($j = 1; $j < strlen($result); $j++) {
                if ($result[$j] == $result[$j - 1]) {
                    $count++;
                } else {
                    $say .= $count . $result[$j - 1];
                    $count = 1;
                }
            }
            $say .= $count . $result[strlen($result) - 1];
            $result = $say;
        }
        return $result;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Approach	Time Complexity: O(2^n). Space Complexity: O(2^n).
Recursive Approach	Time Complexity: O(2^n). Space Complexity: O(2^n) for sequence storage, O(n) recursion stack.
Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative String Simulation	O(n * L)	O(L)	Best general solution. Simple loop that builds each term sequentially with minimal overhead.
Recursive Construction	O(n * L)	O(n + L)	Useful when modeling the sequence definition directly or practicing recursion patterns.

Frequently asked questions

Is Count and Say easy or hard?

Count and Say is typically rated Medium because the logic requires careful grouping of consecutive characters while building new strings. The algorithm itself is straightforward, but off‑by‑one errors and incorrect group handling can make the implementation tricky.

Count and Say Python/Java solution

In Python or Java, iterate through the current string and count consecutive characters. When the character changes, append the count and the digit to a result string or StringBuilder. Repeat this process n-1 times starting from "1" to generate the nth term.

How to solve Count and Say in O(n)?

Strict O(n) time is not achievable because the output string grows with each iteration. The optimal approach is O(n * L), where you iterate n times and process the current string in a single pass. Each pass counts consecutive characters and appends count and digit pairs.

What is the best approach for Count and Say?

The iterative string simulation approach is the most practical solution. Start with "1" and repeatedly scan the current string to count consecutive digits, appending count and digit to form the next term. This runs in O(n * L) time where L is the length of the generated string and uses O(L) space.

Is Count and Say asked at Google/Amazon/Meta?

Count and Say appears in interview practice sets for companies like Amazon, Google, and Microsoft, though it is more commonly used as a warm‑up string problem. It tests the ability to simulate processes, handle consecutive groups, and manipulate strings efficiently.

What data structure is used in Count and Say?

The solution mainly uses string processing with counters. A loop scans the string while tracking the current character and its frequency, then appends the result to a new string or string builder. No complex data structures like hash maps or trees are required.

What is the time complexity of Count and Say?

Time complexity is O(n * L), where n is the requested term and L is the length of the final string. Each iteration scans the current string once to group consecutive digits and build the next string. Space complexity is O(L) for storing the generated term.

Count and Say solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Recursive Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count and Say solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Recursive Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems