DSA Tracker

Visualize

Count and Say

Each term is the previous term read out loud, run by run

time O(n * L) where L is the length of the longest termspace O(L)

There is no formula here and no shortcut: term k only exists once term k-1 has been built, so the work is n-1 rounds of the same tiny job. That job is run-length encoding — sweep the string once, and every time a character repeats, swallow the repeats instead of restarting. The count of a run and the character itself get appended as a pair, which is literally what saying "three ones" writes down as 31. Get the run boundary right and the whole problem is done, because everything else is just doing it again on the result.

Details

Animated on: n = 6 — the sequence starts at "1" and every term describes the one before it, so return the 6th term.

Problem:Count and SayMedium

Each term is the previous term read out loud, run by run

step 1 / 14

1
[0]

Term 1 is the seed "1". Every later term is produced by READING the previous one out loud, so nothing but this string is ever given to us.

Pseudocode
1FUNCTION countAndSay(n):
2  term <- "1"
3  FOR k <- 2 TO n:
4    next <- ""
5    i <- 0
6    WHILE i < LENGTH(term):
7      start <- i
8      WHILE i < LENGTH(term) AND term[i] = term[start]:
9        i <- i + 1
10      APPEND (i - start) AND term[start] TO next
11    term <- next
12  RETURN term

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Term 1 is the seed "1". Every later term is produced by READING the previous one out loud, so nothing but this string is ever given to us.
  2. Reading "1": there is nothing to break the run, so all 1 character is '1'. We write the count 1 then the character '1', so term 2 = "11".
  3. Reading "11": there is nothing to break the run, so all 2 characters are '1'. We write the count 2 then the character '1', so term 3 = "21".
  4. The run of '2' starting at index 0 stops at index 0, because index 1 holds '1', a different character. Its length is 1, so we append the count 1 then the character '2' and the new term reads "12" so far.
  5. The run of '1' starting at index 1 stops at index 1, because the string ends there. Its length is 1, so we append the count 1 then the character '1' and the new term reads "1211" so far.
  6. All 2 runs of "21" are read, so term 4 = "1211". This becomes the string we read next.
  7. The run of '1' starting at index 0 stops at index 0, because index 1 holds '2', a different character. Its length is 1, so we append the count 1 then the character '1' and the new term reads "11" so far.
  8. The run of '2' starting at index 1 stops at index 1, because index 2 holds '1', a different character. Its length is 1, so we append the count 1 then the character '2' and the new term reads "1112" so far.
  9. The run of '1' starting at index 2 stops at index 3, because the string ends there. Its length is 2, so we append the count 2 then the character '1' and the new term reads "111221" so far.
  10. All 3 runs of "1211" are read, so term 5 = "111221". This becomes the string we read next.
  11. The run of '1' starting at index 0 stops at index 2, because index 3 holds '2', a different character. Its length is 3, so we append the count 3 then the character '1' and the new term reads "31" so far.
  12. The run of '2' starting at index 3 stops at index 4, because index 5 holds '1', a different character. Its length is 2, so we append the count 2 then the character '2' and the new term reads "3122" so far.
  13. The run of '1' starting at index 5 stops at index 5, because the string ends there. Its length is 1, so we append the count 1 then the character '1' and the new term reads "312211" so far.
  14. All 3 runs of "111221" are read, so term 6 = "312211" — the answer for n=6.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count and Say in the editorAll Strings problemsBack to roadmap