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":

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)