Count and Say

Med

#0038Time: O(n * L_avg), where L_avg is the average length of the strings. The length of the n-th term grows exponentially (O(ρ^n) where ρ ≈ 1.3). The total time is the sum of processing each term, resulting in a time complexity that is also O(ρ^n).Space: O(L_max + n), where L_max is the length of the longest string generated and n is the recursion depth. The space is required for the recursion call stack and to store the intermediate strings. The length of the n-th term grows exponentially, so this is approximately O(ρ^n) where ρ ≈ 1.3.14 companies

Data structures

String

Companies

Adobe Amazon Apple Bloomberg

Prompt

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 (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "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 <= n <= 30

Follow up: Could you solve it iteratively?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the recursive definition of the count-and-say sequence into a recursive function. The function calls itself to get the previous term in the sequence and then processes that string to generate the current term.

Algorithm

1. Define a function countAndSay(n).
1. If n is 1, return "1" (this is the base case).
1. Otherwise, make a recursive call to countAndSay(n - 1) to get the string from the previous step, let's call it prevStr.
1. Initialize an empty StringBuilder called currentStr to build the new string.
1. Iterate through prevStr using an index i.
1. At each position i, count the number of consecutive occurrences of the character prevStr.charAt(i). Let's say the character is c and it repeats count times.
1. Append the count and the character c to currentStr.
1. Advance the index i by count to move to the next group of different characters.
1. After the loop finishes, convert currentStr to a string and return it.

Walkthrough

The core idea is to rely on the function's ability to call itself. The base case for the recursion is when n is 1, for which the function simply returns "1". For any n > 1, the function first makes a recursive call to countAndSay(n - 1) to obtain the string for the (n-1)-th term. It then iterates through this returned string to perform a run-length encoding. It counts consecutive identical characters and appends the count followed by the character to a new string builder. This process continues until the entire previous string is scanned, and the newly constructed string is returned.

1class Solution {2    public String countAndSay(int n) {3        if (n == 1) {4            return "1";5        }6        7        String prev = countAndSay(n - 1);8        StringBuilder result = new StringBuilder();9        10        int i = 0;11        while (i < prev.length()) {12            char currentChar = prev.charAt(i);13            int count = 0;14            int j = i;15            while (j < prev.length() && prev.charAt(j) == currentChar) {16                count++;17                j++;18            }19            result.append(count);20            result.append(currentChar);21            i = j;22        }23        24        return result.toString();25    }26}

Complexity

Time

O(n * L_avg), where L_avg is the average length of the strings. The length of the n-th term grows exponentially (O(ρ^n) where ρ ≈ 1.3). The total time is the sum of processing each term, resulting in a time complexity that is also O(ρ^n).

Space

O(L_max + n), where L_max is the length of the longest string generated and n is the recursion depth. The space is required for the recursion call stack and to store the intermediate strings. The length of the n-th term grows exponentially, so this is approximately O(ρ^n) where ρ ≈ 1.3.

Trade-offs

Pros

The code is a direct translation of the problem's recursive definition, making it very intuitive and easy to understand.

Cons

Can be less efficient due to the overhead of recursive function calls.
Uses extra space for the recursion call stack, which could lead to a StackOverflowError for very large n (though not an issue with the given constraint of n <= 30).

This approach builds the count-and-say sequence from the ground up, starting from the first term and iteratively generating each subsequent term until the n-th term is reached. This avoids the overhead and potential stack depth issues of recursion, making it more efficient.

Algorithm

1. Handle the base case: if n is 1, return "1".
1. Initialize a string result to "1".
1. Loop with a counter i from 2 to n.
1. Inside the loop, initialize an empty StringBuilder called nextResult to build the next term.
1. Initialize a pointer j = 0 to traverse the current result string.
1. While j is less than the length of result:
- a. Get the character c = result.charAt(j).
- b. Count consecutive occurrences of c starting from j. Let the count be count.
- c. Append count and c to nextResult.
- d. Move the pointer j forward by count.
1. After the inner while loop, update result with the string from nextResult.
1. After the outer for loop finishes, return result.

Walkthrough

Instead of using recursion, we can solve this problem iteratively. We start with the first term, s = "1". We then loop from i = 2 up to n. In each iteration, we generate the i-th term based on the (i-1)-th term (which is stored in s). Inside the loop, we use a StringBuilder to construct the next term. We scan the current string s, counting consecutive characters. For each group of identical consecutive characters, we append the count and the character itself to the StringBuilder. After scanning the entire current string s, the StringBuilder will contain the next term in the sequence. We update s to this new string and continue to the next iteration. After the loop completes, s will hold the n-th term, which we then return.

1class Solution {2    public String countAndSay(int n) {3        if (n == 1) {4            return "1";5        }6        7        String currentStr = "1";8        9        for (int i = 2; i <= n; i++) {10            StringBuilder nextStrBuilder = new StringBuilder();11            int j = 0;12            while (j < currentStr.length()) {13                char currentChar = currentStr.charAt(j);14                int count = 0;15                int k = j;16                while (k < currentStr.length() && currentStr.charAt(k) == currentChar) {17                    count++;18                    k++;19                }20                nextStrBuilder.append(count);21                nextStrBuilder.append(currentChar);22                j = k;23            }24            currentStr = nextStrBuilder.toString();25        }26        27        return currentStr;28    }29}

Complexity

Time

O(n * L_avg), where L_avg is the average length of the strings. The asymptotic complexity is the same as the recursive approach, O(ρ^n), but it is faster in practice due to the absence of function call overhead.

Space

O(L_max), where L_max is the maximum length of the string generated. We only need to store the current string and the next string being built. This is approximately O(ρ^n) where ρ ≈ 1.3.

Trade-offs

Pros

More efficient in terms of both time (no function call overhead) and space (no recursion stack).
Avoids the risk of StackOverflowError that can occur with deep recursion.
Generally considered a better and more robust solution for problems involving linear recursion.

Cons

The code might be slightly less intuitive at first glance compared to the direct recursive translation.

Solutions

Solution

1const countAndSay = function ( n ) { let s = ' 1 ' ; for ( let i = 2 ; i <= n ; i ++ ) { let count = 1 , str = '' , len = s . length ; for ( let j = 0 ; j < len ; j ++ ) { if ( j < len - 1 && s [ j ] === s [ j + 1 ]) { count ++ ; } else { str += ` ${ count }${ s [ j ]} ` ; count = 1 ; } } s = str ; } return s ; };

1using System.Text ; public class Solution { public string CountAndSay ( int n ) { var s = "1" ; while ( n > 1 ) { var sb = new StringBuilder (); var lastChar = '1' ; var count = 0 ; foreach ( var ch in s ) { if ( count > 0 && lastChar == ch ) { ++ count ; } else { if ( count > 0 ) { sb . Append ( count ); sb . Append ( lastChar ); } lastChar = ch ; count = 1 ; } } if ( count > 0 ) { sb . Append ( count ); sb . Append ( lastChar ); } s = sb . ToString (); -- n ; } return s ; } }

1class Solution {2public3  String countAndSay(int n) {4    String s = "1";5    while (--n > 0) {6      StringBuilder t = new StringBuilder();7      for (int i = 0; i < s.length();) {8        int j = i;9        while (j < s.length() && s.charAt(j) == s.charAt(i)) {10          ++j;11        }12        t.append((j - i) + "");13        t.append(s.charAt(i));14        i = j;15      }16      s = t.toString();17    }18    return s;19  }20}

1class Solution { public: string countAndSay ( int n ) { string s = "1" ; while ( -- n ) { string t = "" ; for ( int i = 0 ; i < s . size ();) { int j = i ; while ( j < s . size () && s [ j ] == s [ i ]) ++ j ; t += to_string ( j - i ); t += s [ i ]; i = j ; } s = t ; } return s ; } };

1class Solution:2    # j is now different from i's value t . append ( str ( s [ i ])) i = j s = '' . join ( t ) return s3    def countAndSay(self, n: int) -> str: s = '1' for _ in range(n - 1): i = 0 t = [] while i < len(s): j = i while j < len(s) and s[j] == s[i]: j += 1 t . append(str(j - i))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem