Count And Say

Practice Link

The countAndSay(n) sequence is built iteratively: start with "1", then repeatedly read off the previous string as run-length encoded groups — count how many times each digit repeats consecutively, then emit that count followed by the digit.

n=1  →  "1"
n=2  →  "11"        (one 1)
n=3  →  "21"        (two 1s)
n=4  →  "1211"      (one 2, one 1)
n=5  →  "111221"    (one 1, one 2, two 1s)

Approach#

Build the answer iteratively. Start with str = "1" and loop n-1 times, each time scanning the current string with two pointers to collect runs of identical characters and appending count + digit to the next string.

The inner while walks forward as long as adjacent characters match, incrementing a counter. When the run ends, count + str[i] is appended and the outer loop moves to the next run. Each iteration can at most double the string length, so the strings grow as O(2^n).

class Solution {
public:
    string countAndSay(int n) {
        string str = "1";

        while(--n){
            string ns;
            for(int i = 0; i < str.length(); i++){
                int count = 1;
                while(i + 1 < str.length() && str[i] == str[i+1])
                {
                    count++;
                    i++;
                }
                ns += to_string(count) + str[i];
            }
            str = ns;
        }
        return str;
    }
};

Key Idea:

The core of this problem is simulating the recursive run length encoding process using string manipulation.

Time Complexity: O(n · 2^n) — n iterations, each up to twice the previous string length

Space Complexity: O(2^n) — the output string in the worst case