# Count and Say | LeetCode | InterviewBit | Solution Explained

Count and Say is an interesting problem. It only requires the knowledge of basics of strings and nothing else. I explain the solution simply with code. Problem Links: LeetCode Count and Say InterviewBit Count and Say.

## 0. Count and Say: Problem Discussion

### 0.0. IO Format

• Given: integer n, `1 <= n <= 30`
• Goal: return a string which is: count the number of consecutive characters & say them

### 0.1. Examples

To understand the problem, here are some examples:

## 1. Count and Say: Observations & Logic

### 1.0. Intuitions

All right. What do we observe?

• for getting the answer of n, we need the answer for n-1
• we take the answer of n-1 and create a frequency table for consecutive numbers: for example, if we have `111`, we write it as `(f, x) --> (3, "1") --> "31"` where f is the frequency of the consecutive x numbers.

And that’s all we have to implement!

## 2. Count and Say: Implementation

### 2.0. Code

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

while (n := n-1):
# PART1: FREQUENCY TABLE INTERMEDIATE
table = []
i = 0
while i < len(prev):
table.append([1, prev[i]])
while i+1 < len(prev) and prev[i+1] == prev[i]:
table[-1] += 1
i += 1
i += 1

# PART2: CONVERT BACK TO STRING
prev = "".join(str(f)+x for f, x in table)

return prev
```

### 2.1. Complexity Analysis

• Time: O(NL), N the input given and L the max length of the “prev” string
• Space: O(L), worst case, we have to store a long frequency table of 1 amounts of non-consecutive characters.

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

1. Srishti Chopra :July 23, 2022 at 11:29 am

2. Makarand :August 16, 2022 at 11:06 am
3. Gopal :November 14, 2022 at 5:53 pm