Problem

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 nth element of the count-and-say sequence.

OR

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, …

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Examples

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.

Solution

Method 1 - Recursion

The count-and-say sequence is defined recursively, with countAndSay(1) = "1". Each subsequent term is generated by describing the previous term in terms of the count of consecutive digits. This problem involves generating the nth term in the sequence.

Here is the approach:

  1. Base Case: If n is 1, return “1”.
  2. Recursive Generation:
    • Start with the initial string “1”.
    • For each term from 2 to n, generate the next term by reading the current term and applying run-length encoding.
  3. Run-Length Encoding:
    • Traverse the string, count consecutive identical digits, and construct the next term by appending the count and the digit.

Code

Java
class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";

        String ans = "1";
        for (int i = 2; i <= n; i++) {
            ans = nextTerm(ans);
        }

        return ans;
    }

    private String nextTerm(String s) {
        StringBuilder sb = new StringBuilder();
        int count = 1;
        char prev = s.charAt(0);

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == prev) {
                count++;
            } else {
                sb.append(count).append(prev);
                count = 1;
                prev = s.charAt(i);
            }
        }

        sb.append(count).append(prev);
        return sb.toString();
    }
}
Python
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1: 
            return "1"
        
        ans: str = "1"
        for _ in range(2, n + 1):
            ans = self.next_term(ans)
        
        return ans

    def next_term(self, s: str) -> str:
        ans: str = ""
        count: int = 1
        prev: str = s[0]

        for i in range(1, len(s)):
            if s[i] == prev:
                count += 1
            else:
                ans += str(count) + prev
                count = 1
                prev = s[i]

        ans += str(count) + prev
        return ans

Complexity

  • ⏰ Time complexity: O(m * n), where m is the maximum length of the string encountered up to the nth term, and n is the input number. Generating each term involves processing the entire previous term.
  • 🧺 Space complexity: O(m), where m is the length of the term being generated. Each new term is stored temporarily.

Method 2 - Iteration

The problem can be solved by using a simple iteration. The sequence starts with “1”, and each subsequent term is derived by describing the previous term in terms of consecutive digit counts.

Here is the approach:

  1. Base Case: If n is less than or equal to 0, return an empty string.
  2. Initialization: Start with the initial term “1”.
  3. Generate Terms:
    • Use a while loop to generate terms from 2 to n.
    • For each term, use a StringBuilder to construct the next term.
    • Traverse the current term and count consecutive identical digits.
    • Append the count and digit to the StringBuilder.
    • Update the result with the new term and increment i.
  4. Return the Result: After generating the required term, return it as a string.

Code

Java
class Solution {

	public String countAndSay(int n) {
		if (n<= 0)
			return "";
	
		String result = "1";
		int i = 1;
	
		while (i<n) {
			StringBuilder sb = new StringBuilder();
			int count = 1;
			for (int j = 1; j<result.length(); j++) {
				if (result.charAt(j) == result.charAt(j - 1)) {
					count++;
				} else {
					sb.append(count);
					sb.append(result.charAt(j - 1));
					count = 1;
				}
			}
	
			sb.append(count);
			sb.append(result.charAt(result.length() - 1));
			result = sb.toString();
			i++;
		}
	
		return result;
	}
}
Python
class Solution:
    def countAndSay(self, n: int) -> str:
        if n <= 0:
            return ""
        
        result: str = "1"
        i: int = 1
        
        while i < n:
            sb: List[str] = []
            count: int = 1
            for j in range(1, len(result)):
                if result[j] == result[j - 1]:
                    count += 1
                else:
                    sb.append(str(count))
                    sb.append(result[j - 1])
                    count = 1
            
            sb.append(str(count))
            sb.append(result[-1])
            result = "".join(sb)
            i += 1
        
        return result

Complexity

  • ⏰ Time complexity: O(m * n)
  • 🧺 Space complexity: O(m)