  # LeetCode - Count and Say

## Problem statement

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 substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

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.

Problem statement taken from: https://leetcode.com/problems/count-and-say

Example 1:

``````Input: n = 1
Output: '1'
Explanation: This is the base case.
``````

Example 2:

``````Input: n = 4
Output: '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'
``````

Constraints:

``- 1 <= n <= 30``

### Explanation

#### Brute force approach

A naive approach is to generate all the terms from 1 to n. We generate the next term using the current term by scanning it left to right. While scanning it, we keep track of the count of all consecutive characters. For the matching characters, we append the count of the character and append the character to the count.

A C++ snippet of this approach is as follows:

``````string countAndSay(int n) {
if (n == 1) {
return '1';
}
if (n == 2) {
return '11';
}

string current = '11';
string tmp = '';
int counter = 1;
int len;

for (int i = 3; i <= n; i++) {
current += '\$';
len = str.length();

counter = 1;
tmp = '';

for (int j = 1; j < len; j++) {
if (current[j] != current[j - 1]) {
tmp += counter + '0';
tmp += current[j-1];
counter = 1;
} else {
counter++;
}
}

current = tmp;
}

return current;
}``````

The time complexity of this approach is O(n^2). The space complexity is O(1).

#### Dynamic Programming

We can use Dynamic Programming to generate each row of the count and say pattern based on the previous row. We store all the results in a vector of strings to avoid repeating the same calculations for multiple rows. This will reduce the overall time complexity of the solution.

Let's check the algorithm to understand it better.

#### Algorithm

``````- initialize a vector of string
vector<string> dp(n + 1, '')

set dp = '1'

initialize current and next string
string current, next;

set counter to 1
int counter = 1

- loop for i = 2; i <= n; i++
- set current = dp[i - 1]
- set next = ''
- set counter = 1

- loop for j = 1; j < current.size(); j++
- if current[j - 1] == current[j]
- update counter = counter + 1
- else
- update next = next + to_string(counter) + current[j - 1]
- set counter = 1
- if end

- update next = next + to_string(counter) + current.back()

- dp[i] = next
- for end

- for end

- return dp[n]
``````

#### C++ solution

``````class Solution {
public:
string countAndSay(int n) {
vector<string> dp(n + 1, '');
dp = '1';
string current, next;
int counter;

for(int i = 2; i <= n; i++) {
current = dp[i - 1];
next = '';

counter = 1;

for(int j = 1; j < current.size(); j++) {
if(current[j - 1] == current[j]) {
counter++;
} else {
next += to_string(counter) + current[j - 1];
counter = 1;
}
}

next += to_string(counter) + current.back();

dp[i] = next;
}

return dp[n];
}
};``````

#### Golang solution

``````func countAndSay(n int) string {
dp := make([]string, n + 1)
dp = '1'
var current, next string
counter := 1

for i := 2; i <= n; i++ {
current = dp[i - 1]
next = ''

counter = 1

for j := 1; j < len(current); j++ {
if current[j - 1] == current[j] {
counter++
} else {
next += strconv.Itoa(counter) + string(current[j - 1])
counter = 1
}
}

next += strconv.Itoa(counter) + current[len(current) - 1:]

dp[i] = next
}

return dp[n]
}``````

#### JavaScript solution

``````var countAndSay = function(n) {
let dp = new Array(n + 1).fill('');
dp = '1';
let current, next;
let counter;

for(let i = 2; i <= n; i++) {
current = dp[i - 1];
next = '';

counter = 1;

for(let j = 1; j < current.length; j++) {
if(current[j - 1] == current[j]) {
counter++;
} else {
next += counter.toString() + current[j - 1];
counter = 1;
}
}

next += counter.toString() + current.slice(-1);

dp[i] = next;
}

return dp[n];
};``````

#### Dry Run

Let's dry-run our algorithm for a few examples to see how the solution works.

``````Input: n = 4

Step 1: vector<string> dp(n + 1, '')
dp(4 + 1, '')
dp(5, '')
dp = ['', '', '', '', '']
dp = '1'
dp = ['', '1', '', '', '']

string current, next
int counter

Step 2: loop for i = 2; i <= n
2 <= 4
true

current = dp[i - 1]
= dp[2 - 1]
= dp
= '1'
next = ''

counter = 1

loop for j = 1; j < current.size()
1 < 1
false

next = next + to_string(counter) + current.back()
= '' + to_string(1) + '1'
= '' + '1' + '1'
= '11'

dp[i] = next
dp = '11'

dp = ['', '1', '11', '', '']

i++
i = 3

Step 3: loop for i <= n
3 <= 4
true

current = dp[i - 1]
= dp[3 - 1]
= dp
= '11'
next = ''

counter = 1

loop for j = 1; j < current.size()
1 < 2
true

if current[j - 1] == current[j]
current[1 - 1] == current
current == current
'1' == '1'
true

counter++
counter = 2

i++
i = 2

loop for j < current.size()
2 < 2
false

next = next + to_string(counter) + current.back()
= '' + to_string(2) + '1'
= '' + '2' + '1'
= '21'

dp[i] = next
dp = '21'

dp = ['', '1', '11', '21', '']

i++
i = 4

Step 4: loop for i <= n
4 <= 4
true

current = dp[i - 1]
= dp[4 - 1]
= dp
= '21'
next = ''

counter = 1

loop for j = 1; j < current.size()
1 < 2
true

if current[j - 1] == current[j]
current[1 - 1] == current
current == current
'2' == '1'
false
else
next = next + to_string(counter) + current[j - 1]
= '' + to_string(1) + current[1 - 1]
= '' + '1' + '2'
= '12'

counter = 1

j++
j = 2

loop for j < current.size()
2 < 2
false

next = next + to_string(counter) + current.back()
= '12' + to_string(1) + '1'
= '' + '1' + '1'
= '1211'

dp[i] = next
dp = '1211'

dp = ['', '1', '11', '21', '1211']

i++
i = 5

Step 5: loop for i <= n
5 <= 4
false

Step 6: return dp[n]
dp

We return the answer as '1211'.
``````