# Leetcode 38: Count and Say

Let’s solve a medium problem together on Leetcode.com: Count and Say

## Description

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

`countAndSay(1) = "1"`

`countAndSay(n)` is the way you would "say" the digit string from `countAndSay(n-1)`, which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string `"3322251"`:

Given a positive integer `n`, return the `nth` term of the count-and-say sequence.

Example:

`Input: n = 4Output: "1211"Explanation:countAndSay(1) = "1"countAndSay(2) = say "1" = one 1 = "11"countAndSay(3) = say "11" = two 1's = "21"countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"`

## Solution

For a given string, in order to “Count and Say” it, there are two variables to consider:

• count of the current character
• what’s the current character?

Assume the string we’re visiting is “1211”, let’s have two variables `count` and `previous` to record the result while iterating the string.

• Step 1: initialization

Before visiting the string, let’s say `count = 0` and `previous = ‘.’` to represent the initial state and a variable `result` to denote the output.

• Step 2: visit index 0, character = ‘1’

Now, the current character we’re visiting is ‘1’. `prevous = ‘.’` is denoting the current character is the beginning of the string, we simply increment the `count` by 1 and set the `previous = ‘1’` for the next visiting character.

• Step 3: visit index 1, character = ‘2’

The current character we’re visiting is ‘2’. `prevous = ‘1’` is denoting the current character is a new character we need to “count and say”. Now, we need to do two things: 1). record the previous result: append `count` and `previous` to the result. After appending, `result = ‘11’`; 2). renew `count = 1`, and `prevous = ‘2’` for the next visiting character.

• Step 4: visit index 2, character = ‘1’

The current character we’re visiting is ‘1’. `prevous = ‘2’` is denoting the current character is a new character we need to “count and say”. Now, we need to do two things: 1). record the previous result: append `count` and `previous` to the result. After appending, `result = ‘1112’`; 2). renew `count = 1`, and `prevous = ‘1’` for the next visiting character.

• Step 5: visit index 3, character = ‘1’

The current character we’re visiting is ‘1’ is the same with `prevous = ‘1’` . We increment the `count = 2` variable and leave the `previous`.

• Step 6: done iteration

After iterating the string, we still need to append the last visiting's result to the output: `result = ‘111221’` . Depending on the iteration times, we’ll decide whether return the `result` or input it as a string for the next iteration.

## Code

`def countAndSay(n: int) -> str:    res = '1'    for _ in range(1, n):        prev, count = '.', 0        curr_str = ""        for char in res:            if char == prev or prev == '.':                count += 1            else:                curr_str += str(count) + prev                count = 1            prev = char        curr_str += str(count) + prev        res = curr_str    return res`

## Reference

on the way to become a programmer

Get the Medium app