Count and Say problem

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 to "say" a digit string, split it into groups of consecutive identical digits. Then for each group, say the count followed by the digit.

Example:

• countAndSay(1) = "1" (base case)
• countAndSay(2) = "11" (one 1)
• countAndSay(3) = "21" (two 1s)
• countAndSay(4) = "1211" (one 2, one 1)
• countAndSay(5) = "111221" (one 1, one 2, two 1s)
• countAndSay(6) = "312211" (three 1s, two 2s, one 1)

Approach 1: Iterative

Intuition

Start with "1" and iteratively build each subsequent string by reading the previous one. Count consecutive identical characters and append the count followed by the character.

Algorithm

1. Start with result = "1"
2. For each level from 2 to n:
   • Read the current result string
   • Count consecutive identical characters
   • Build the next string with count + character
3. Return the final result

public class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";
        
        String result = "1";
        
        for (int i = 2; i <= n; i++) {
            StringBuilder next = new StringBuilder();
            int count = 1;
            char current = result.charAt(0);
            
            for (int j = 1; j < result.length(); j++) {
                if (result.charAt(j) == current) {
                    count++;
                } else {
                    next.append(count).append(current);
                    current = result.charAt(j);
                    count = 1;
                }
            }
            
            // Don't forget the last group
            next.append(count).append(current);
            result = next.toString();
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n * m) where m is the length of the string at each level (grows exponentially)
• Space Complexity: O(m) for storing the current and next strings

Approach 2: Recursive

Intuition

Use recursion to build the sequence. The base case is n=1 returning "1". For n > 1, recursively get the (n-1)th term and "say" it.

Algorithm

1. Base case: if n == 1, return "1"
2. Recursively get countAndSay(n-1)
3. Process the result to generate the nth term
4. Return the generated string

public class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";
        
        String prev = countAndSay(n - 1);
        return sayString(prev);
    }
    
    private String sayString(String s) {
        StringBuilder result = new StringBuilder();
        int count = 1;
        char current = s.charAt(0);
        
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == current) {
                count++;
            } else {
                result.append(count).append(current);
                current = s.charAt(i);
                count = 1;
            }
        }
        
        result.append(count).append(current);
        return result.toString();
    }
}

Complexity Analysis

• Time Complexity: O(n * m) where m is the average length of strings
• Space Complexity: O(n * m) for recursion stack and strings

Approach 3: Using Two Pointers for Counting

Intuition

Use two pointers to find groups of consecutive identical characters more elegantly.

public class Solution {
    public String countAndSay(int n) {
        String result = "1";
        
        for (int i = 1; i < n; i++) {
            StringBuilder next = new StringBuilder();
            int j = 0;
            
            while (j < result.length()) {
                char current = result.charAt(j);
                int count = 0;
                
                // Count consecutive characters
                while (j < result.length() && result.charAt(j) == current) {
                    count++;
                    j++;
                }
                
                next.append(count).append(current);
            }
            
            result = next.toString();
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(m) for the result string

Sequence Properties

The Count and Say sequence has interesting properties:

1. Only contains digits 1, 2, and 3
2. The length approximately grows by factor of 1.303577... (Conway's constant)
3. Related to the Look-and-Say sequence studied by John Conway

First 10 terms:

Key Takeaways

1. Run-length encoding is the core concept behind this problem
2. Iterative approach is generally more efficient than recursive
3. Always remember to process the last group after the loop ends
4. Using StringBuilder (Java) or direct string concatenation strategies matters for performance
5. The sequence grows exponentially, so n > 30 will produce very long strings
6. This is a classic interview question testing string manipulation and attention to detail