Count and Say
On this page 
Problem Statement
The "Count and Say" sequence is a sequence of digit strings that is defined recursively. Here's how it works:
countAndSay(1) starts with the string "1".
For any number n greater than 1, countAndSay(n) is obtained by describing the digits of countAndSay(n - 1). This is done using a technique called run-length encoding (RLE).
Run-Length Encoding (RLE): This is a method where you count consecutive identical characters in a string and then encode them as the count followed by the character. For example, if you have the string "3322251":
"33" is encoded as "23" (2 occurrences of '3')
"222" is encoded as "32" (3 occurrences of '2')
"5" is encoded as "15" (1 occurrence of '5')
"1" is encoded as "11" (1 occurrence of '1')
Putting it all together, the RLE of "3322251" would be "23321511".
Objective:
Given a positive integer n, return the nth term in the "Count and Say" sequence.
Example 1
Input: n = 1
Output: "1"
Example 2
Input: n = 4
Output: "1211"
Solution 1: Iterative Approach
function countAndSay(n) {
function generateNextSequence(currentSequence) {
let result = "";
let index = 0;
while (index < currentSequence.length) {
let count = 1;
while (index + 1 < currentSequence.length && currentSequence[index] === currentSequence[index + 1]) {
index++;
count++;
}
result += count + currentSequence[index];
index++;
}
return result;
}
let sequence = "1";
for (let i = 2; i <= n; i++) {
sequence = generateNextSequence(sequence);
}
return sequence;
}
const n1 = 1;
countAndSay(n1); //output: 1
const n2 = 4;
countAndSay(n2); //output: 1211
Solution 2: Recursive Approach
function countAndSayRecursive(n) {
if (n === 1) return "1";
function generateNextSequence(currentSequence) {
let result = "";
let index = 0;
while (index < currentSequence.length) {
let count = 1;
while (index + 1 < currentSequence.length && currentSequence[index] === currentSequence[index + 1]) {
index++;
count++;
}
result += count + currentSequence[index];
index++;
}
return result;
}
return generateNextSequence(countAndSay(n - 1));
}
const n1 = 1;
countAndSayRecursive(n1); //output: 1
const n2 = 4;
countAndSayRecursive(n2); //output: 1211
Solution 3: Dynamic Programming
function countAndSayDynamicProgramming(n) {
const sequences = ["1"];
function generateNextSequence(currentSequence) {
let result = "";
let index = 0;
while (index < currentSequence.length) {
let count = 1;
while (index + 1 < currentSequence.length && currentSequence[index] === currentSequence[index + 1]) {
index++;
count++;
}
result += count + currentSequence[index];
index++;
}
return result;
}
for (let i = 1; i < n; i++) {
sequences.push(generateNextSequence(sequences[i - 1]));
}
return sequences[n - 1];
}
const n1 = 1;
countAndSayDynamicProgramming(n1); //output: 1
const n2 = 4;
countAndSayDynamicProgramming(n2); //output: 1211
Solution 4: Using a Queue
function countAndSayUsingQueue(n) {
if (n === 1) return "1";
let currentSequence = "1";
for (let i = 1; i < n; i++) {
let newSequence = "";
let index = 0;
while (index < currentSequence.length) {
let count = 1;
while (index + 1 < currentSequence.length && currentSequence[index] === currentSequence[index + 1]) {
index++;
count++;
}
newSequence += count + currentSequence[index];
index++;
}
currentSequence = newSequence;
}
return currentSequence;
}
const n1 = 1;
countAndSayUsingQueue(n1); //output: 1
const n2 = 4;
countAndSayUsingQueue(n2); //output: 1211
Solution 5: Using Array to Build Result
function countAndSayArray(n) {
if (n === 1) return "1";
let currentSequence = "1";
for (let i = 1; i < n; i++) {
let parts = [];
let index = 0;
while (index < currentSequence.length) {
let count = 1;
while (index + 1 < currentSequence.length && currentSequence[index] === currentSequence[index + 1]) {
index++;
count++;
}
parts.push(count + currentSequence[index]);
index++;
}
currentSequence = parts.join("");
}
return currentSequence;
}
const n1 = 1;
countAndSayArray(n1); //output: 1
const n2 = 4;
countAndSayArray(n2); //output: 1211
Solution 6: Optimized Space Complexity
function countAndSayOptimized(n) {
if (n === 1) return "1";
let currentSequence = "1";
for (let i = 1; i < n; i++) {
let newSequence = "";
let index = 0;
while (index < currentSequence.length) {
let count = 1;
while (index + 1 < currentSequence.length && currentSequence[index] === currentSequence[index + 1]) {
index++;
count++;
}
newSequence += count + currentSequence[index];
index++;
}
currentSequence = newSequence;
}
return currentSequence;
}
const n1 = 1;
countAndSayOptimized(n1); //output: 1
const n2 = 4;
countAndSayOptimized(n2); //output: 1211
Solution 7: Functional Programming Approach
function countAndSayFunctionalProgramming(n) {
if (n === 1) return "1";
const generateNextSequence = (sequence) => {
let result = "";
let index = 0;
while (index < sequence.length) {
let count = 1;
while (index + 1 < sequence.length && sequence[index] === sequence[index + 1]) {
index++;
count++;
}
result += count + sequence[index];
index++;
}
return result;
};
let currentSequence = "1";
Array.from({ length: n - 1 }).forEach(() => {
currentSequence = generateNextSequence(currentSequence);
});
return currentSequence;
}
const n1 = 1;
countAndSayFunctionalProgramming(n1); //output: 1
const n2 = 4;
countAndSayFunctionalProgramming(n2); //output: 1211