Count and Say - Practice Coding Problems

Count and Say - Problem

String Medium

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"
countAndSay(n) is the run-length encoding of countAndSay(n - 1)

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters with the concatenation of the count and the character.

For example, to compress the string "3322251":

"33" becomes "23" (two 3's)
"222" becomes "32" (three 2's)
"5" becomes "15" (one 5)
"1" becomes "11" (one 1)

Thus the compressed string becomes "23321511".

Given a positive integer n, return the nth element of the count-and-say sequence.

Input & Output

Example 1 — Basic Case

$ Input: n = 1

› Output: "1"

💡 Note: Base case: countAndSay(1) is defined as "1"

Example 2 — Second Term

$ Input: n = 4

› Output: "1211"

💡 Note: countAndSay(1) = "1", countAndSay(2) = "11" (one 1), countAndSay(3) = "21" (two 1s), countAndSay(4) = "1211" (one 2, one 1)

Example 3 — Longer Sequence

$ Input: n = 5

› Output: "111221"

💡 Note: countAndSay(4) = "1211", so countAndSay(5) describes "1211" as "111221" (one 1, one 2, two 1s)

Constraints

1 ≤ n ≤ 30

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=4, need 4th term of sequence

Process

Build each term by describing the previous

Output

Return the nth term of the sequence

Key Takeaway

🎯 Key Insight: Each term describes the previous term by counting consecutive identical digits

Asked in

F Facebook 45 G Google 35

The key insight is to iteratively apply run-length encoding, counting consecutive identical characters and building the description string. The optimal approach uses StringBuilder for efficient string construction. Time: O(n×m), Space: O(m) where m is the result string length.

Common Approaches

Approach	Time	Space	Notes
✓ Iterative String Building	O(n × m)	O(m)	Build each sequence step by step from n=1 to target n
StringBuilder Approach	O(n × m)	O(m)	Use StringBuilder/StringBuffer for efficient string concatenation

Iterative String Building — Algorithm Steps

Start with base case: "1"
For each step from 2 to n, apply run-length encoding
Scan current string, count consecutive characters
Build new string with count + character pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Start with "1"

Base case for n=1

Count and Say

Read current string, count consecutive chars

Build Next

Concatenate count + character pairs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(int n) {
    if (n == 1) {
        char* result = malloc(2);
        strcpy(result, "1");
        return result;
    }
    
    char* current = malloc(1000);
    strcpy(current, "1");
    
    for (int i = 2; i <= n; i++) {
        char* next = malloc(1000);
        next[0] = '\0';
        int j = 0;
        int len = strlen(current);
        
        while (j < len) {
            int count = 1;
            char ch = current[j];
            while (j + 1 < len && current[j + 1] == ch) {
                count++;
                j++;
            }
            char temp[10];
            sprintf(temp, "%d%c", count, ch);
            strcat(next, temp);
            j++;
        }
        
        free(current);
        current = next;
    }
    
    return current;
}

int main() {
    int n;
    scanf("%d", &n);
    char* result = solution(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n iterations, each processing string of average length m

✓ Linear Growth

Space Complexity

O(m)

Storage for current and next string, where m is the length of result string

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Iterative String Building — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler