# 0038. Count and Say

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Count and Say](https://leetcode.com/problems/count-and-say/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0038-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 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 groups so that each group is a contiguous section all of the **same character.** Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

{% hint style="info" %}
**Refer to examples for a more clear explanation.**
{% endhint %}
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= n <= 30`

```python
# n = 1
1      #

# n = 2
11     # one 1's

# n = 3
21     # two 1's

# n = 4
1211   # one 2, and one 1.

# n = 5
111221 # one 1, one 2, and two 1's.
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
Referring to **each char in the previous sequence** and **record the previous char** to check whether we need to **do accumulation or restart the counter with the new previous char**.

```python
s = '1'      # base case
s = '11'     # preChar = 1, do accumulation because s[i] == s[i+1]
s = '21'     # preChar = 2, restart counter because s[i] != s[i+1]

s = '1211'   # preChar = 1, counter = 1  ->  f'{counter}{preChar}'
             # preChar = 2, counter = 1
             # preChar = 1, counter = 2
             
s = '111221' # preChar = 1, counter = 3  ->  f'{counter}{preChar}' 
             # preChar = 2, counter = 2
             # preChar = 1, counter = 1
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def countAndSay(self, n: int) -> str:
        # (base case)
        if n == 1: return '1'
        
        # ==================================================
        #  String + Math                                   =
        # ==================================================
        # time  : O(nk)
        # space : O(1)
        
        ret = '1'
        
        for _ in range(n - 1):
            prev, counter = ret[0], 0
            tmp = ''
            
            for c in ret:
                if prev != c:
                    tmp += str(counter) + prev
                    prev, counter = c, 1
                else:
                    counter += 1
                    
            tmp += str(counter) + prev
            ret = tmp
            
        return ret
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(nk)
     * @space : O(1)
     */

    public String countAndSay(int n) {
        String ret = "1";
        
        /* base case */
        if(n == 1) return ret;
        
        for(int i=0 ; i<n-1 ; i++) {
            StringBuilder tmp = new StringBuilder();
            char prev = ret.charAt(0);
            int counter = 0;
            
            for(int j=0 ; j<ret.length() ; j++) {
                if(prev != ret.charAt(j)) {
                    tmp.append(counter);
                    tmp.append(prev);
                    prev = ret.charAt(j);
                    counter = 1;
                } else {
                    counter++;
                }
            }
            
            tmp.append(counter);
            tmp.append(prev);
            ret = tmp.toString();
        }
        
        return ret;
    }
}
```

{% endtab %}
{% endtabs %}