Count and Say

Generate the nth term of the count-and-say sequence.

Language Selection

Choose your preferred programming language

Showing: Python

Count and Say

Problem Statement

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

countAndSay(1) = "1"
countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

Examples

Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1s = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Example 3:

Input: n = 5
Output: "111221"
Explanation:
countAndSay(5) = say "1211" = one 1 + one 2 + two 1s = "11" + "12" + "21" = "111221"

Constraints

1 <= n <= 30

Approach 1: Recursive with String Building (Optimal)

Algorithm

Use recursion to build the sequence step by step. For each step, count consecutive identical digits and build the next string.

Steps:

Base case: n = 1 returns “1”
Recursively get the previous string
Count consecutive identical digits
Build the next string by appending count + digit

Implementation

Python:

def countAndSay(n):
    """
    Generate the nth term of count-and-say sequence
    Time: O(4^n/3) - exponential growth
    Space: O(4^n/3) - recursion stack and string storage
    """
    if n == 1:
        return "1"
    
    # Get previous string recursively
    prev = countAndSay(n - 1)
    
    # Build current string
    result = ""
    i = 0
    
    while i < len(prev):
        # Count consecutive identical digits
        count = 1
        while i + count < len(prev) and prev[i] == prev[i + count]:
            count += 1
        
        # Append count and digit
        result += str(count) + prev[i]
        i += count
    
    return result

Java:

class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        
        // Get previous string recursively
        String prev = countAndSay(n - 1);
        
        // Build current string
        StringBuilder result = new StringBuilder();
        int i = 0;
        
        while (i < prev.length()) {
            // Count consecutive identical digits
            int count = 1;
            while (i + count < prev.length() && prev.charAt(i) == prev.charAt(i + count)) {
                count++;
            }
            
            // Append count and digit
            result.append(count).append(prev.charAt(i));
            i += count;
        }
        
        return result.toString();
    }
}

Go:

func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    
    // Get previous string recursively
    prev := countAndSay(n - 1)
    
    // Build current string
    var result strings.Builder
    i := 0
    
    for i < len(prev) {
        // Count consecutive identical digits
        count := 1
        for i+count < len(prev) && prev[i] == prev[i+count] {
            count++
        }
        
        // Append count and digit
        result.WriteString(strconv.Itoa(count))
        result.WriteByte(prev[i])
        i += count
    }
    
    return result.String()
}

JavaScript:

function countAndSay(n) {
    if (n === 1) {
        return "1";
    }
    
    // Get previous string recursively
    const prev = countAndSay(n - 1);
    
    // Build current string
    let result = "";
    let i = 0;
    
    while (i < prev.length) {
        // Count consecutive identical digits
        let count = 1;
        while (i + count < prev.length && prev[i] === prev[i + count]) {
            count++;
        }
        
        // Append count and digit
        result += count + prev[i];
        i += count;
    }
    
    return result;
}

C#:

public class Solution {
    public string CountAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        
        // Get previous string recursively
        string prev = CountAndSay(n - 1);
        
        // Build current string
        StringBuilder result = new StringBuilder();
        int i = 0;
        
        while (i < prev.Length) {
            // Count consecutive identical digits
            int count = 1;
            while (i + count < prev.Length && prev[i] == prev[i + count]) {
                count++;
            }
            
            // Append count and digit
            result.Append(count).Append(prev[i]);
            i += count;
        }
        
        return result.ToString();
    }
}

Complexity Analysis

Time Complexity: O(4^n/3) - The sequence grows exponentially
Space Complexity: O(4^n/3) - Recursion stack and string storage

Approach 2: Iterative Approach

Algorithm

Build the sequence iteratively without recursion to avoid stack overflow issues.

Steps:

Start with “1” as the base case
For each step from 2 to n, build the next string
Count consecutive identical digits and append count + digit

Implementation

Python:

def countAndSayIterative(n):
    """
    Iterative approach to generate count-and-say sequence
    Time: O(4^n/3)
    Space: O(4^n/3)
    """
    if n == 1:
        return "1"
    
    current = "1"
    
    for _ in range(2, n + 1):
        next_str = ""
        i = 0
        
        while i < len(current):
            # Count consecutive identical digits
            count = 1
            while i + count < len(current) and current[i] == current[i + count]:
                count += 1
            
            # Append count and digit
            next_str += str(count) + current[i]
            i += count
        
        current = next_str
    
    return current

Java:

public String countAndSayIterative(int n) {
    if (n == 1) {
        return "1";
    }
    
    String current = "1";
    
    for (int step = 2; step <= n; step++) {
        StringBuilder nextStr = new StringBuilder();
        int i = 0;
        
        while (i < current.length()) {
            // Count consecutive identical digits
            int count = 1;
            while (i + count < current.length() && current.charAt(i) == current.charAt(i + count)) {
                count++;
            }
            
            // Append count and digit
            nextStr.append(count).append(current.charAt(i));
            i += count;
        }
        
        current = nextStr.toString();
    }
    
    return current;
}

Go:

func countAndSayIterative(n int) string {
    if n == 1 {
        return "1"
    }
    
    current := "1"
    
    for step := 2; step <= n; step++ {
        var nextStr strings.Builder
        i := 0
        
        for i < len(current) {
            // Count consecutive identical digits
            count := 1
            for i+count < len(current) && current[i] == current[i+count] {
                count++
            }
            
            // Append count and digit
            nextStr.WriteString(strconv.Itoa(count))
            nextStr.WriteByte(current[i])
            i += count
        }
        
        current = nextStr.String()
    }
    
    return current
}

JavaScript:

function countAndSayIterative(n) {
    if (n === 1) {
        return "1";
    }
    
    let current = "1";
    
    for (let step = 2; step <= n; step++) {
        let nextStr = "";
        let i = 0;
        
        while (i < current.length) {
            // Count consecutive identical digits
            let count = 1;
            while (i + count < current.length && current[i] === current[i + count]) {
                count++;
            }
            
            // Append count and digit
            nextStr += count + current[i];
            i += count;
        }
        
        current = nextStr;
    }
    
    return current;
}

C#:

public string CountAndSayIterative(int n) {
    if (n == 1) {
        return "1";
    }
    
    string current = "1";
    
    for (int step = 2; step <= n; step++) {
        StringBuilder nextStr = new StringBuilder();
        int i = 0;
        
        while (i < current.Length) {
            // Count consecutive identical digits
            int count = 1;
            while (i + count < current.Length && current[i] == current[i + count]) {
                count++;
            }
            
            // Append count and digit
            nextStr.Append(count).Append(current[i]);
            i += count;
        }
        
        current = nextStr.ToString();
    }
    
    return current;
}

Complexity Analysis

Time Complexity: O(4^n/3) - Still exponential growth
Space Complexity: O(4^n/3) - String storage

Key Insights

Sequence Growth: The sequence grows exponentially (approximately 4^n/3)
Recursive Nature: Each term depends on the previous term
String Building: Efficient string concatenation is crucial
Pattern Recognition: Understanding the count-and-say pattern
Base Case: n = 1 is always “1”

Edge Cases

n = 1: Returns “1” (base case)
n = 2: Returns “11” (one 1)
n = 3: Returns “21” (two 1s)
Large n: Exponential growth makes large n impractical
String Length: Strings become very long for large n

Test Cases

def test_countAndSay():
    # Basic cases
    assert countAndSay(1) == "1"
    assert countAndSay(2) == "11"
    assert countAndSay(3) == "21"
    assert countAndSay(4) == "1211"
    assert countAndSay(5) == "111221"
    
    # Additional cases
    assert countAndSay(6) == "312211"
    assert countAndSay(7) == "13112221"
    assert countAndSay(8) == "1113213211"
    
    print("All tests passed!")

test_countAndSay()

Follow-up Questions

Reverse Count and Say: Given a string, find which n it corresponds to?
Count and Say with Different Base: What if we start with a different base string?
Count and Say with Different Rules: What if we change the counting rules?
Performance Optimization: How can we optimize for very large n?
Pattern Analysis: What patterns exist in the sequence?

Common Mistakes

Base Case Handling: Not properly handling n = 1
String Concatenation: Inefficient string building
Index Bounds: Not checking array bounds when counting
Recursion Depth: Not considering stack overflow for large n
Pattern Understanding: Misunderstanding the count-and-say pattern

Interview Tips

Explain the Pattern: Walk through the sequence step by step
Discuss Complexity: Mention exponential growth
Handle Edge Cases: Always check n = 1
Optimize String Building: Use StringBuilder for efficiency
Consider Alternatives: Discuss iterative vs recursive approaches