Count and Say

Description

38. Count and Say

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 each maximal group of consecutive identical characters with the concatenation of the length of the group followed by the character itself. For example, to compress "3322251", replace "33" with "23", "222" with "32", "5" with "15", and "1" with "11". Thus the compressed string becomes "23321511".

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

Example 1:
Input: n = 4
Output: "1211"

Explanation:
countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

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

Constraints:

• $1\le n\le 30$

---

Run-Length Encoding (RLE) is a simple data compression method that replaces long runs of repeated characters with a count followed by the character itself.
Instead of storing repeating data individually, you group identical consecutive items and describe them in pairs: [Count][Character].

Basic Example

• Original String: AAAAABBBCC
• Identified Groups: AAAAA (5 ‘A’s), BBB (3 ‘B’s), CC (2 ‘C’s)
• RLE Compressed: 5A3B2C

Numerical Example (Count and Say)

• Original String: "3322251"
• Identified Groups: "33", "222", "5", "1"
• Count & Replace:
  • "33" $\to$ 2 threes $\to$ "23"
  • "222" $\to$ 3 twos $\to$ "32"
  • "5" $\to$ 1 five $\to$ "15"
  • "1" $\to$ 1 one $\to$ "11"
• RLE Compressed: "23321511"

Strengths & Weaknesses

• Best used for: Data with lots of consecutive repeating characters (like black-and-white image bitmaps, icons, or simple continuous signals).
• Worst used for: Data with no consecutive repetitions (e.g., "ABCDEF" compresses to "1A1B1C1D1E1F", which doubles the size).

Approach 1: Iterative Simulation (Most Optimized — $O(M)$ Time, $O(M)$ Space)

Intuition

Start with the base string "1" and iteratively construct the sequence $n-1$ times:

1. Maintain a pointer through the current string to group consecutive identical characters.
2. Count how many times a digit repeats (count).
3. Append the count followed by the digit to a StringBuilder.
4. Update the sequence string for the next iteration.

class Solution {
    public String countAndSay(int n) {
        String result = "1";
 
        for (int i = 1; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            int count = 1;
 
            for (int j = 0; j < result.length(); j++) {
                // If the next character is identical, increment count
                if (j + 1 < result.length() && result.charAt(j) == result.charAt(j + 1)) {
                    count++;
                } else {
                    // Group ended: append count and the character
                    sb.append(count).append(result.charAt(j));
                    count = 1;
                }
            }
 
            result = sb.toString();
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(M)$ — Where $M$ is the length of the $n$-th sequence string. Because the sequence length grows exponentially by a factor of roughly $1.3$, the work done at step $n$ dominates the total time ($M\le 4462$ for $n=30$).
• Space Complexity: $O(M)$ — To build and store the string representation at step $n$.

---

Approach 2: Top-Down Recursion ($O(M)$ Time, $O(M)$ Space)

Intuition

Recursively compute countAndSay(n - 1) until reaching base case n = 1. Once countAndSay(n - 1) returns, apply run-length encoding on the result using a linear sweep.

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

Complexity

• Time Complexity: $O(M)$ — Sum of sequence lengths across all recursive calls bounded by $O(M)$.
• Space Complexity: $O(M)$ — Requires $O(N)$ stack space for recursion depth plus $O(M)$ auxiliary memory for string construction.

---

Easy Memory Rule

“Count consecutive matching digits $\to$ append [count][digit] to form the next term!”