Count and Say

Medium

Problem

The count-and-say sequence starts with "1". Each next term reads the previous term aloud, group by group: "1" is read as "one 1" → "11", which is read as "two 1s" → "21", and so on. Given n, return the nth term.

Example 1

Input:  n = 4
Output: "1211"

1 → 11 → 21 → 1211 ("one 2, one 1").

Also asked as: Count and Say problem

Test cases

Case 1

Input:    4
Expected: "1211"

Case 2

Input:    5
Expected: "111221"

Case 3

Input:    6
Expected: "312211"

Case 4

Input:    1
Expected: "1"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Iterative run-length encoding

Time O(n · length)Space O(length)

Start from "1"; each next term describes the previous as "<count><digit>" runs.

function countAndSay(n) {
let s = '1';
for (let k = 1; k < n; k++) {
let next = '', i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) j++;
next += (j - i) + s[i];
i = j;
}
s = next;
}
return s;
}