38. Count and Say
The count-and-say sequence is what you get by repeatedly reading a string of digits out loud. It starts from the string "1". To go from one term to the next, sweep the current term left to right, cut it into maximal runs of identical digits, and speak each run as count, then digit:
"1"is one 1 →"11""11"is two 1s →"21""21"is one 2, one 1 →"1211""1211"is one 1, one 2, two 1s →"111221"
Given an integer n, return the n-th term of this sequence as a string, counting from count_and_say(1) = "1".
Example 1:
Input: n = 1
Output: "1"
Explanation: The sequence is defined to start at "1", so the first term needs no reading at all.
Example 2:
Input: n = 4
Output: "1211"
Explanation: Term 1 is "1"; reading it gives "11" (term 2); reading that gives "21" (term 3); reading "21" — one 2, then one 1 — gives "1211".
Example 3:
Input: n = 6
Output: "312211"
Explanation: Term 5 is "111221": three 1s, two 2s, one 1 — spoken aloud that is "312211".
Constraints:
- 1 ≤ n ≤ 30
- The answer for n = 30 is a few thousand characters long — build terms, don't try to precompute by hand.
Hints:
There is no closed form worth chasing — simulate. Start from "1" and apply the read-aloud transformation n − 1 times.
One transformation is a run-length scan: anchor an index i at the start of a run, advance j while the digit repeats, append str(j − i) followed by the digit, then jump i to j. Collect pieces in a list/StringBuilder — repeated string concatenation is the classic quadratic trap here.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 1
Expected output: "1"