# 38. Count and Say LeetCode Solution

In this guide we will provide 38. Count and Say LeetCode Solution with best time and space complexity. The solution to Count and Say problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

## Table of Contents

- Problem Statement
- Count and Say solution in C++
- Count and Say soution in Java
- Count and Say solution Python
- Additional Resources

## Problem Statement of Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = “1”

countAndSay(n) is the run-length encoding of countAndSay(n – 1).

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string “3322251” we replace “33” with “23”, replace “222” with “32”, replace “5” with “15” and replace “1” with “11”. Thus the compressed string becomes “23321511”.

Given a positive integer n, return the nth element of the count-and-say sequence.

Example 1:

Input: n = 4

Output: “1211”

Explanation:

countAndSay(1) = “1”

countAndSay(2) = RLE of “1” = “11”

countAndSay(3) = RLE of “11” = “21”

countAndSay(4) = RLE of “21” = “1211”

Example 2:

Input: n = 1

Output: “1”

Explanation:

This is the base case.

Constraints:

1 <= n <= 30

Follow up: Could you solve it iteratively?

### Complexity Analysis

**Time Complexity:**O(|\texttt{ans}|)**Space Complexity:**O(|\texttt{ans}|)

## 38. Count and Say LeetCode Solution in C++

```
class Solution {
public:
string countAndSay(int n) {
string ans = "1";
while (--n > 0) {
string next;
for (int i = 0; i < ans.length(); ++i) {
int count = 1;
while (i + 1 < ans.length() && ans[i] == ans[i + 1]) {
++count;
++i;
}
next += to_string(count) + ans[i];
}
ans = std::move(next);
}
return ans;
}
};
```

/* code provided by PROGIEZ */

## 38. Count and Say LeetCode Solution in Java

```
class Solution {
public String countAndSay(int n) {
StringBuilder sb = new StringBuilder("1");
while (--n > 0) {
StringBuilder next = new StringBuilder();
for (int i = 0; i < sb.length(); ++i) {
int count = 1;
while (i + 1 < sb.length() && sb.charAt(i) == sb.charAt(i + 1)) {
++count;
++i;
}
next.append(count).append(sb.charAt(i));
}
sb = next;
}
return sb.toString();
}
}
```

// code provided by PROGIEZ

## 38. Count and Say LeetCode Solution in Python

```
class Solution:
def countAndSay(self, n: int) -> str:
ans = '1'
for _ in range(n - 1):
nxt = ''
i = 0
while i < len(ans):
count = 1
while i + 1 < len(ans) and ans[i] == ans[i + 1]:
count += 1
i += 1
nxt += str(count) + ans[i]
i += 1
ans = nxt
return ans
```

#code by PROGIEZ

## Additional Resources

- Explore all Leetcode problems solutions at Progiez here
- Explore all problems on Leetcode website here

Feel free to give suggestions! Contact Us