Count and Say

medium

Last Updated - 02/09/2024

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