# LeetCode 38: Count and Say

## Problem Restatement

We are given a positive integer `n`.

We need to return the `n`th term of the count-and-say sequence.

The sequence starts with:

```python
countAndSay(1) = "1"
```

For every `n > 1`, the next term is built by reading the previous term using run-length encoding.

Run-length encoding means grouping consecutive equal digits, then writing:

```python
count + digit
```

For example:

```python
"111221"
```

has groups:

```python
"111", "22", "1"
```

So it becomes:

```python
"31" + "22" + "11" = "312211"
```

The constraint is:

```python
1 <= n <= 30
```

The problem statement defines the sequence recursively by `countAndSay(1) = "1"` and `countAndSay(n)` as the run-length encoding of `countAndSay(n - 1)`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | The `n`th term as a string |
| Base case | `countAndSay(1) = "1"` |
| Transformation | Run-length encode the previous term |
| Constraint | `1 <= n <= 30` |

Function shape:

```python
def countAndSay(n: int) -> str:
    ...
```

## Examples

Example 1:

```python
n = 1
```

The first term is defined as:

```python
"1"
```

Return:

```python
"1"
```

Example 2:

```python
n = 4
```

Build the sequence:

```python
1: "1"
2: "11"
3: "21"
4: "1211"
```

Explanation:

```python
"1"    -> one 1          -> "11"
"11"   -> two 1s         -> "21"
"21"   -> one 2, one 1   -> "1211"
```

Return:

```python
"1211"
```

Example 3:

```python
n = 5
```

The fourth term is:

```python
"1211"
```

Read it as:

```python
one 1, one 2, two 1s
```

So the fifth term is:

```python
"111221"
```

## First Thought: Simulate the Definition

The definition already tells us how to build the sequence.

Start from `"1"`.

Then repeat `n - 1` times:

1. Read the current string from left to right.
2. Group consecutive equal digits.
3. For each group, append the group length and the digit.
4. Replace the current string with the new string.

For example, from:

```python
current = "3322251"
```

The groups are:

| Group | Count | Output |
|---|---:|---|
| `"33"` | `2` | `"23"` |
| `"222"` | `3` | `"32"` |
| `"5"` | `1` | `"15"` |
| `"1"` | `1` | `"11"` |

So:

```python
"3322251" -> "23321511"
```

## Key Insight

Each step is just a scan over the previous string.

We do not need recursion, and we do not need to store every term.

We only keep the current term.

To encode one term, use a pointer `i`.

At position `i`, find how far the current run of equal digits goes.

For example:

```python
current = "111221"
           ^
           i
```

The digit is `"1"`.

Move another pointer `j` until the digit changes.

```python
"111221"
 ^^^
 i j
```

The run has length `3`, so append:

```python
"31"
```

Then continue from the next run.

## Algorithm

Initialize:

```python
current = "1"
```

Repeat `n - 1` times:

1. Create an empty list `parts`.
2. Set `i = 0`.
3. While `i < len(current)`:
   - Set `j = i`.
   - Move `j` while `current[j] == current[i]`.
   - The count is `j - i`.
   - Append `str(count)` and `current[i]`.
   - Set `i = j`.
4. Join `parts` into the next string.
5. Assign it back to `current`.

Return `current`.

## Correctness

The sequence definition says that every term after the first is the run-length encoding of the previous term.

The algorithm starts with the correct first term, `"1"`.

During one transformation, the inner loop partitions the current string into maximal consecutive groups of equal digits. For each group, it appends exactly the number of digits in that group followed by the digit itself. That is precisely the required run-length encoding.

After one iteration, `current` becomes the next term of the sequence. After `n - 1` iterations, `current` has advanced from the first term to the `n`th term.

Therefore, the returned string is exactly `countAndSay(n)`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(total generated length)` | We scan each generated term once |
| Space | `O(length of nth term)` | We store the current term and the next term |

For this problem, `n <= 30`, so direct simulation is sufficient.

## Implementation

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

        for _ in range(n - 1):
            parts = []
            i = 0

            while i < len(current):
                j = i

                while j < len(current) and current[j] == current[i]:
                    j += 1

                count = j - i
                parts.append(str(count))
                parts.append(current[i])

                i = j

            current = "".join(parts)

        return current
```

## Code Explanation

Start from the first term:

```python
current = "1"
```

We need to transform it `n - 1` times.

```python
for _ in range(n - 1):
```

Use a list instead of repeated string concatenation.

```python
parts = []
```

The pointer `i` marks the start of the current run.

```python
i = 0
```

The pointer `j` moves until the run ends.

```python
while j < len(current) and current[j] == current[i]:
    j += 1
```

The run length is:

```python
count = j - i
```

Append the count and the digit.

```python
parts.append(str(count))
parts.append(current[i])
```

Then move to the next run.

```python
i = j
```

After all runs are encoded, build the next term.

```python
current = "".join(parts)
```

Return the final term.

```python
return current
```

## Testing

```python
def check(n: int, expected: str) -> None:
    actual = Solution().countAndSay(n)
    assert actual == expected, (n, actual, expected)

def run_tests():
    check(1, "1")
    check(2, "11")
    check(3, "21")
    check(4, "1211")
    check(5, "111221")
    check(6, "312211")
    check(7, "13112221")

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Base case |
| `n = 2` | First transformation |
| `n = 3` | Counts a repeated digit |
| `n = 4` | Counts two separate groups |
| `n = 5` | Counts a run of two `1`s |
| `n = 6` | Counts multiple run lengths |
| `n = 7` | Confirms repeated simulation |