Count and Say

Problem

The "count-and-say" sequence starts with "1"; each next term describes the previous term by counting consecutive digit runs. Given n, return the nth term.

Input:  n = 4
Output: "1211"
(1 -> "11" -> "21" -> "1211")

Python Solution

def count_and_say(n):
    result = "1"
    for _ in range(n - 1):
        next_term = []
        i = 0
        while i < len(result):
            count = 1
            while i + 1 < len(result) and result[i] == result[i + 1]:
                i += 1
                count += 1
            next_term.append(str(count) + result[i])
            i += 1
        result = "".join(next_term)
    return result

C++ Solution

string countAndSay(int n) {
    string result = "1";
    for (int k = 1; k < n; k++) {
        string next;
        int i = 0;
        while (i < result.size()) {
            int count = 1;
            while (i + 1 < result.size() && result[i] == result[i + 1]) {
                i++; count++;
            }
            next += to_string(count) + result[i];
            i++;
        }
        result = next;
    }
    return result;
}

Java Solution

class Solution {
    public String countAndSay(int n) {
        String result = "1";
        for (int k = 1; k < n; k++) {
            StringBuilder next = new StringBuilder();
            int i = 0;
            while (i < result.length()) {
                int count = 1;
                while (i + 1 < result.length() && result.charAt(i) == result.charAt(i + 1)) {
                    i++; count++;
                }
                next.append(count).append(result.charAt(i));
                i++;
            }
            result = next.toString();
        }
        return result;
    }
}

Complexity

Time: O(n · L) — where L is the length of the term at each of the n-1 steps, since each term is built by scanning the previous one. Space: O(L) for the term being built at each step; the sequence's terms grow, but not exponentially in practice for small n.