The look-and-say next term

Question

The look-and-say sequence builds each term by reading the previous one aloud in runs: "1211" is "one 1, one 2, two 1s," which you write as "111221". Given one term (a string of digits), produce the next term.

"1"       ->  "11"        # one 1
"1211"    ->  "111221"    # one 1, one 2, two 1s
"111221"  ->  "312211"    # three 1s, two 2s, one 1

Return the next term in $O(n)$ time.

Accepted Answer

This is run-length encoding with the count written before the character. Walk the string once, tracking the current run's digit and length. When the digit changes, flush count + digit to the output and reset. The classic bug is forgetting the final flush after the loop. Tracing "1211": the runs are 1 (once), 2 (once), 1 (twice), so we emit "11", "12", "21", joined as "111221". Feeding that back in yields "312211". Time O(n), space O(n) for the output. Note the counts here are always small, but as with any run encoder the safe habit is to write the count as a string, not assume a single digit.…

The look-and-say next term

Your answer

More Coding questions