# 10.Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:\
1\
11\
21\
1211\
111221

**Explanation:**

`1` is read off as `"one 1"` or `11`.\
`11` is read off as `"two 1s"` or `21`.\
`21` is read off as `"one 2`, then `one 1"` or `1211`.

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

## **Solution:** 

**Intuition:**

For example, the saying and conversion for digit string `"3322251"`:![](https://assets.leetcode.com/uploads/2020/10/23/countandsay.jpg)

```cpp
class Solution
{
public:
    string countAndSay(int n)
    {

        if (n == 1)
        {
            return "1";
        }
        if (n == 2)
        {
            return "11";
        }
        
        int j;
        string a = "11";
        for (int i = 3; i <= n; i++)
        {
            string temp = "";
            int count = 1;
            for (j = 1; j < a.length(); j++)
            {

                if (a[j] != a[j - 1])
                {

                    temp = temp + to_string(count) + a[j - 1];
                    count = 1;
                }
                else if (a[j] == a[j - 1])
                {
                    count++;
                }
            }

            temp = temp + to_string(count) + a[j - 1];
            a = temp;
        }
        return a;
    }
};
```

**Time Complexity: O(n^2)**