LeetCode Problem

Problem Description

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 you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

Examples

Input: n = 1
Output: "1"

Input: n = 4
Output: "1211"

Constraints

1 <= n <= 30

Follow-up

Approach to Solve

Use recursion to generate the sequence, and iterate through the previous string to count and say the digits.

Code Implementation

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        prev = self.countAndSay(n - 1)
        result = ""
        count = 1
        for i in range(1, len(prev)):
            if prev[i] == prev[i-1]:
                count += 1
            else:
                result += str(count) + prev[i-1]
                count = 1
        result += str(count) + prev[-1]
        return result

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

class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) return "1";
        string prev = countAndSay(n - 1);
        string result;
        int count = 1;
        for (int i = 1; i < prev.length(); i++) {
            if (prev[i] == prev[i - 1]) {
                count++;
            } else {
                result += to_string(count) + prev[i - 1];
                count = 1;
            }
        }
        result += to_string(count) + prev.back();
        return result;
    }

Explanation

This solution uses recursion to generate the count-and-say sequence. Here's a detailed explanation of the algorithm:

Base case: If n is 1, return "1".
Recursive step: Generate the (n-1)th term by calling countAndSay(n-1).
Iterate through the (n-1)th term:
- Count consecutive identical digits.
- When a different digit is encountered or we reach the end, append the count and the digit to the result.
Return the generated nth term.

The time and space complexity are both O(2^n) in the worst case, as the length of the sequence can potentially double with each step.

Complexity

Time Complexity: O(2^n)
Space Complexity: O(2^n)

LeetSolved

Count and Say