51. Count and Say Sequence

The count-and-say sequence starts with '1'. Each subsequent term is generated by describing the previous term's runs of consecutive identical digits, as '<count><digit>' pairs, concatenated in order. Given n, print the nth term (1-indexed).

Input: The input is a single line containing the integer n. Output: Print the nth term of the count-and-say sequence as a string of digits.

1 <= n <= 30

The sequence's growth is deceptively slow at first, then accelerates in complexity - this is a great example of a rule so simple to state ('just describe the previous term') producing surprisingly complex-looking results after just a handful of steps.

Starting from '1', build each next term by literally describing the previous term out loud: how many of each digit appear in a row, and which digit it is. Brute force: There isn't really a 'faster' way to skip ahead to term n directly - each term genuinely depends on fully describing the one before it, so you must build all n terms in sequence; the only real choice is how efficiently you build each individual term's description. Optimised: Building each term with a single linear scan (grouping consecutive equal digits as you go, rather than repeatedly re-scanning) keeps each step's cost proportional only to that term's own length - since terms can grow, the overall cost across all n steps is bounded by the total length of all terms combined, which stays very manageable for n up to 30.

There is no need to ever keep more than the current term in memory: generate term k from term k-1 using a two-pointer scan (one pointer marks the start of a run, a second advances until the run ends) that writes directly into a fresh buffer, then discard the previous term entirely before moving to term k+1. This keeps the same O(L) per-term cost as the buffer approach but reduces overall memory use, since only the current and next term ever coexist rather than accumulating history, which matters when n is at its upper bound and terms grow long. Time: O(n * L) Space: O(L)

Keep the same run-length-encoding logic (scan for runs of identical digits, emit count then digit) but write each piece into a mutable buffer such as a StringBuilder or character array instead of concatenating immutable strings. Appending to a mutable buffer is amortized O(1) per character, so building each term now costs O(L) instead of O(L^2), and the total cost across all n terms drops accordingly. The algorithm's logic is unchanged; only the data structure used to assemble output is smarter. Time: O(n * L) Space: O(L)

Starting from the term '1', repeatedly build the next term from the current one: scan through it, and every time a run of identical digits ends, append its count and the digit itself onto a growing result using plain string concatenation (the '+' operator). Since strings are immutable, each concatenation allocates and copies a brand new string, so building a term of length L this way costs O(L^2) instead of O(L). This produces the correct nth term, it's just wasteful about how it assembles the output. Time: O(n * L^2) where L is the length of the longest term Space: O(L)

1. Start with the string '1' (the first term). 2. To build the next term, scan the current term left to right, grouping consecutive identical digits together. 3. For each group, write down its count followed by the digit itself, and concatenate all these pieces together - that's the next term. 4. Repeat this process (n-1) times starting from '1' to reach the nth term.

Time: Proportional to the combined length of all n terms generated along the way - each term is built with one linear scan of the previous one. Space: Proportional to the length of the longest term generated, which grows slowly for the given constraint (n <= 30).

n = 1 (output is just '1'); n = 30, where the term becomes very long, testing performance of repeated run-length generation.

Be ready to clarify explicitly that terms are ALWAYS built sequentially from term 1 - there's no shortcut to computing term 30 without first computing terms 1 through 29 in order.