Count and say

Problem Statement

The Count and Say sequence is defined as:

1

11

21

1211

111221

...

Each term is generated by describing the previous term.

Return the nᵗʰ term.

---

Brute Force Intuition

In an interview, you can explain it like this:

Start from "1" and repeatedly generate the next term by counting consecutive identical digits.

Since every term depends only on the previous one, we simulate the process.

Complexity

• Time Complexity: O(N × L)
• Space Complexity: O(L)

Where:

• N = Term Number
• L = Length of the Generated String

---

Moving Towards the Optimal Approach

Observe the pattern:

1

↓

One 1

↓

11

↓

Two 1's

↓

21

↓

One 2

One 1

↓

1211

Each term is built by:

Count Consecutive Characters

↓

Append Count

↓

Append Character

---

Pattern Recognition

Whenever you see:

• Consecutive Characters
• Run-Length Encoding
• String Simulation

Think:

Two Pointers / String Traversal

---

Key Observation

Traverse the previous string.

For every group of consecutive characters:

Count Frequency

↓

Append Count

↓

Append Character

Move to the next group.

---

Optimal Approach

Start with:

"1"

Repeat:

Generate Next String

until reaching the nᵗʰ term.

---

Optimal Java Solution

class Solution {

    public String countAndSay(int n) {

        String ans = "1";

        for (int i = 2; i <= n; i++) {

            StringBuilder curr = new StringBuilder();

            int count = 1;

            for (int j = 1; j <= ans.length(); j++) {

                if (j < ans.length() &&
                    ans.charAt(j) == ans.charAt(j - 1)) {

                    count++;

                } else {

                    curr.append(count);
                    curr.append(ans.charAt(j - 1));

                    count = 1;
                }
            }

            ans = curr.toString();
        }

        return ans;
    }
}

---

Dry Run

Input

n = 5

Sequence:

1

↓

11

↓

21

↓

1211

↓

111221

Answer:

111221

---

Why This Works?

Every term depends only on the previous one.

For each group of consecutive digits:

Frequency

+

Digit

forms the next sequence.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N × L)
Space Complexity	O(L)

Where L is the maximum length of the generated string.

---

Interview One-Liner

Simulate the sequence by traversing the previous term, counting consecutive characters, and appending the count followed by the character.

---

Pattern Learned

Consecutive Characters

↓

Count Frequency

↓

Build Next String

Similar Problems

• Count and Say
• String Compression
• Run-Length Encoding
• Decode String

---

Memory Trick

Think:

Read Previous String

↓

Count Same Digits

↓

Write

Count + Digit

Mental Model

111221

↓

Three 1's

↓

One 2

↓

Two 1's

↓

312211

Whenever you hear:

"Count and Say"

your brain should immediately think:

Group Consecutive Characters + String Simulation