# 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][0] += 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.

### Recommended Posts

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

June 13, 2022

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

June 13, 2022

Please write the proof.

This solution need an amendment for 2 digit number.