Leetcode 38: Count and Say

 

1. Problem Statement (Simple Explanation):

We define a sequence of strings countAndSay(n):

• Base:

• countAndSay(1) = "1"

• Recursive:

• countAndSay(n) = RLE(countAndSay(n-1))

• where RLE = run-length encoding of the previous term.

Run-Length Encoding (RLE) here means:

• Read the string left to right.

• Group consecutive identical characters.

• For each group k of character c, append:

• the count k followed by the character c.

Example of RLE:

• "3322251":

• "33" → "23" (two 3s)

• "222" → "32" (three 2s)

• "5" → "15" (one 5)

• "1" → "11" (one 1)

• Combined: "23321511".

You must return countAndSay(n) as a string.

2. Examples:

Example 1:

Input: n = 4

Sequence:

• n = 1: "1"

• n = 2: RLE("1") → one 1 → "11"

• n = 3: RLE("11") → two 1s → "21"

• n = 4: RLE("21") → one 2, then one 1 → "12" + "11" = "1211"

Output: "1211"

Example 2:

Input: n = 1

Output: "1" (Base case.)

3. Approach – Iterative Generation (Recommended):

We generate the sequence iteratively from 1 up to n.

Idea:

• Start with current = "1".

• For step from 2 to n:

• Set current = RLE(current).

RLE helper:

Given a string s, produce its run-length encoding:

1. Initialize an empty result builder.

2. Iterate over s with index i:

• Set count = 1.

• While i + 1 < len(s) and s[i+1] == s[i], increment count and i.

• Append count (as string) and s[i] to result.

3. Return the result as a string.

Pseudo-code:

Complexity:

Let Lk = length(countAndSay(k)). Empirically, Lk stays manageable for n <= 30.

For each step:

• We scan the current string once.

Total complexity:

• Time: Approximately O(k=1nLk); for n <= 30, this is very safe.

• Space: O(L*k) for the final string.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code: