---
tags: data_structure_python
---
# Count and Say <img src="https://img.shields.io/badge/-easy-brightgreen">
The count-and-say sequence is the sequence of integers with the first five terms as following:
```
1. 1
2. 11
3. 21
4. 1211
5. 111221
```
```1``` is read off as ```"one 1"``` or ```11```.
```11``` is read off as ```"two 1s"``` or ```21```.
```21``` is read off as ```"one 2```, then ```one 1"``` or ```1211```.
Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.
Note: Each term of the sequence of integers will be represented as a string.
<ins>**Example 1:**</ins>
>Input: 1
>Output: "1"
>Explanation: This is the base case.
<ins>**Example 2:**</ins>
>Input: 4
>Output: "1211"
>Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".
## Solution
```python=
class Solution:
def __countAndSay(self, n, prev):
if n == 1:
return "1"
prev = self.__countAndSay(n-1, prev)
res, tmp, frequency = "", prev[0], 0
for i in range(len(prev)):
# Count.
if prev[i] == tmp:
frequency += 1
else:
res = res + str(frequency) + prev[i-1]
frequency = 1
tmp = prev[i]
# Say.
if i == len(prev)-1:
res = res + str(frequency) + prev[i]
return res
def countAndSay(self, n: int) -> str:
return self.__countAndSay(n, "")
```
Sign in with Wallet
Connect another wallet