---
# System prepended metadata

title: 'Count and Say <img src="https://img.shields.io/badge/-easy-brightgreen">'
tags: [data_structure_python]

---

---
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, "")
```