# Count and Say
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-and-say)
Canonical: https://scaleengineer.com/dsa/problems/count-and-say
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [PayPal](https://scaleengineer.com/companies/paypal), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [Pinterest](https://scaleengineer.com/companies/pinterest), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
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](http://en.wikipedia.org/wiki/Run-length%5Fencoding) (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?

# Approaches
## Recursive Approach
This approach directly translates the recursive definition of the count-and-say sequence into a recursive function. The function calls itself to get the previous term in the sequence and then processes that string to generate the current term.
**Time:** O(n * L_avg), where L_avg is the average length of the strings. The length of the n-th term grows exponentially (O(ρ^n) where ρ ≈ 1.3). The total time is the sum of processing each term, resulting in a time complexity that is also O(ρ^n). · **Space:** O(L_max + n), where L_max is the length of the longest string generated and n is the recursion depth. The space is required for the recursion call stack and to store the intermediate strings. The length of the n-th term grows exponentially, so this is approximately O(ρ^n) where ρ ≈ 1.3.
**Pros:** The code is a direct translation of the problem's recursive definition, making it very intuitive and easy to understand.
**Cons:** Can be less efficient due to the overhead of recursive function calls.; Uses extra space for the recursion call stack, which could lead to a `StackOverflowError` for very large `n` (though not an issue with the given constraint of `n <= 30`).
### Explanation
The core idea is to rely on the function's ability to call itself. The base case for the recursion is when `n` is 1, for which the function simply returns "1". For any `n > 1`, the function first makes a recursive call to `countAndSay(n - 1)` to obtain the string for the `(n-1)`-th term. It then iterates through this returned string to perform a run-length encoding. It counts consecutive identical characters and appends the count followed by the character to a new string builder. This process continues until the entire previous string is scanned, and the newly constructed string is returned.

```java
class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        
        String prev = countAndSay(n - 1);
        StringBuilder result = new StringBuilder();
        
        int i = 0;
        while (i < prev.length()) {
            char currentChar = prev.charAt(i);
            int count = 0;
            int j = i;
            while (j < prev.length() && prev.charAt(j) == currentChar) {
                count++;
                j++;
            }
            result.append(count);
            result.append(currentChar);
            i = j;
        }
        
        return result.toString();
    }
}
```
### Algorithm
- 1. Define a function `countAndSay(n)`.
- 2. If `n` is 1, return "1" (this is the base case).
- 3. Otherwise, make a recursive call to `countAndSay(n - 1)` to get the string from the previous step, let's call it `prevStr`.
- 4. Initialize an empty `StringBuilder` called `currentStr` to build the new string.
- 5. Iterate through `prevStr` using an index `i`.
- 6. At each position `i`, count the number of consecutive occurrences of the character `prevStr.charAt(i)`. Let's say the character is `c` and it repeats `count` times.
- 7. Append the `count` and the character `c` to `currentStr`.
- 8. Advance the index `i` by `count` to move to the next group of different characters.
- 9. After the loop finishes, convert `currentStr` to a string and return it.

## Iterative Approach
This approach builds the count-and-say sequence from the ground up, starting from the first term and iteratively generating each subsequent term until the n-th term is reached. This avoids the overhead and potential stack depth issues of recursion, making it more efficient.
**Time:** O(n * L_avg), where L_avg is the average length of the strings. The asymptotic complexity is the same as the recursive approach, O(ρ^n), but it is faster in practice due to the absence of function call overhead. · **Space:** O(L_max), where L_max is the maximum length of the string generated. We only need to store the current string and the next string being built. This is approximately O(ρ^n) where ρ ≈ 1.3.
**Pros:** More efficient in terms of both time (no function call overhead) and space (no recursion stack).; Avoids the risk of `StackOverflowError` that can occur with deep recursion.; Generally considered a better and more robust solution for problems involving linear recursion.
**Cons:** The code might be slightly less intuitive at first glance compared to the direct recursive translation.
### Explanation
Instead of using recursion, we can solve this problem iteratively. We start with the first term, `s = "1"`. We then loop from `i = 2` up to `n`. In each iteration, we generate the `i`-th term based on the `(i-1)`-th term (which is stored in `s`). Inside the loop, we use a `StringBuilder` to construct the next term. We scan the current string `s`, counting consecutive characters. For each group of identical consecutive characters, we append the count and the character itself to the `StringBuilder`. After scanning the entire current string `s`, the `StringBuilder` will contain the next term in the sequence. We update `s` to this new string and continue to the next iteration. After the loop completes, `s` will hold the `n`-th term, which we then return.

```java
class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        
        String currentStr = "1";
        
        for (int i = 2; i <= n; i++) {
            StringBuilder nextStrBuilder = new StringBuilder();
            int j = 0;
            while (j < currentStr.length()) {
                char currentChar = currentStr.charAt(j);
                int count = 0;
                int k = j;
                while (k < currentStr.length() && currentStr.charAt(k) == currentChar) {
                    count++;
                    k++;
                }
                nextStrBuilder.append(count);
                nextStrBuilder.append(currentChar);
                j = k;
            }
            currentStr = nextStrBuilder.toString();
        }
        
        return currentStr;
    }
}
```
### Algorithm
- 1. Handle the base case: if `n` is 1, return "1".
- 2. Initialize a string `result` to "1".
- 3. Loop with a counter `i` from 2 to `n`.
- 4. Inside the loop, initialize an empty `StringBuilder` called `nextResult` to build the next term.
- 5. Initialize a pointer `j = 0` to traverse the current `result` string.
- 6. While `j` is less than the length of `result`:
  - a. Get the character `c = result.charAt(j)`.
  - b. Count consecutive occurrences of `c` starting from `j`. Let the count be `count`.
  - c. Append `count` and `c` to `nextResult`.
  - d. Move the pointer `j` forward by `count`.
- 7. After the inner while loop, update `result` with the string from `nextResult`.
- 8. After the outer for loop finishes, return `result`.

# Solutions
### JavaScript

```javascript
const countAndSay = function ( n ) { let s = ' 1 ' ; for ( let i = 2 ; i <= n ; i ++ ) { let count = 1 , str = '' , len = s . length ; for ( let j = 0 ; j < len ; j ++ ) { if ( j < len - 1 && s [ j ] === s [ j + 1 ]) { count ++ ; } else { str += ` ${ count }${ s [ j ]} ` ; count = 1 ; } } s = str ; } return s ; };
```

### CSharp

```csharp
using System.Text ; public class Solution { public string CountAndSay ( int n ) { var s = "1" ; while ( n > 1 ) { var sb = new StringBuilder (); var lastChar = '1' ; var count = 0 ; foreach ( var ch in s ) { if ( count > 0 && lastChar == ch ) { ++ count ; } else { if ( count > 0 ) { sb . Append ( count ); sb . Append ( lastChar ); } lastChar = ch ; count = 1 ; } } if ( count > 0 ) { sb . Append ( count ); sb . Append ( lastChar ); } s = sb . ToString (); -- n ; } return s ; } }
```

### Java

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

```

### CPP

```cpp
class Solution { public: string countAndSay ( int n ) { string s = "1" ; while ( -- n ) { string t = "" ; for ( int i = 0 ; i < s . size ();) { int j = i ; while ( j < s . size () && s [ j ] == s [ i ]) ++ j ; t += to_string ( j - i ); t += s [ i ]; i = j ; } s = t ; } return s ; } };
```

### Python

```python
class Solution:
    # j is now different from i's value t . append ( str ( s [ i ])) i = j s = '' . join ( t ) return s
    def countAndSay(self, n: int) -> str: s = '1' for _ in range(n - 1): i = 0 t = [] while i < len(s): j = i while j < len(s) and s[j] == s[i]: j += 1 t . append(str(j - i))

```