36. Count and Say

Start from "1" and repeatedly describe the previous term: group consecutive equal digits and emit count followed by the digit.

Say what you see

Beginning with "1", produce each next term by run-length encoding the current one: scan runs of identical digits and append count + digit.

s = "1"
repeat n-1 times:
    walk runs of s; append str(runLength) + digit

Worked example

1 → 11 (one 1) → 21 (two 1s) → 1211 (one 2, one 1) → 111221 → ...

Complexity

• Time: O(n · length) where length grows roughly like 1.3^n.
• Space: O(length).

class Solution {
    public String countAndSay(int n) {
        String s = "1";
        for (int t = 1; t < n; t++) {
            StringBuilder sb = new StringBuilder();
            int i = 0;
            while (i < s.length()) {
                int j = i;
                while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
                sb.append(j - i).append(s.charAt(i));
                i = j;
            }
            s = sb.toString();
        }
        return s;
    }
}