**source:**https://leetcode.com/problems/count-and-say/**C/C++**

**Solution to LeetCode**problem

**38**.

**Count And Say**.

## Problem

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 n^{th} term of the count-and-say sequence*.

## Examples

**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`

## Solution

- We iterate through the string, if
`size == 0`

then the string will be`"1"`

. - We count how many times a character is repeated.
- Append to the final string the
`counter + the character`

. - Call recursively the method, passing our last generated string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
private:
string cAndS(int n, string cStr) {
if (n==0)
return cStr;
string tmp = cStr.size() == 0 ? "1"s : ""s;
for (int i=0; i<cStr.size(); i++) {
int j=i+1;
while(j<cStr.size() && cStr[j] == cStr[i])
j++;
tmp += to_string(j-i) + cStr[i];
i = j-1;
}
return cAndS(n-1, tmp);
}
public:
string countAndSay(int n) {
return cAndS(n, "");
}
};