Count and Say

115.Count and Say

String

Problem Statement:

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the description of the previous term in the sequence (n-1), where each digit is counted and described consecutively.

Given an integer n, return the nth term of the count-and-say sequence.

Algorithm:

1. Initialize the sequence with "1" for n = 1.
2. Iteratively build the sequence up to the nth term:
   • For each term, use a helper function to read and count consecutive digits of the current sequence.
   • For each group of consecutive digits:
     • Append the count followed by the digit to form the new term.
3. Return the sequence at the nth step.

Complexity:

Time: O(m × n), where m is the average length of terms and n is the input | Space: O(m), where m is the length of the current term.

Java Implementation:

public class Solution {
    public String countAndSay(int n) {
        String s = "1"; // Start with the first term
        for (int i = 2; i <= n; i++) {
            s = countIdx(s); // Generate the next term
        }
        return s;
    }

    // Helper function to generate the next term based on the current term
    public String countIdx(String s) {
        StringBuilder sb = new StringBuilder();
        char c = s.charAt(0);
        int count = 1;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                count++; // Increment count if the current character matches
            } else {
                sb.append(count).append(c); // Append count and character
                c = s.charAt(i); // Update to the next character
                count = 1; // Reset count
            }
        }
        sb.append(count).append(c); // Append the last group
        return sb.toString();
    }
}
                

Python Implementation:

def countAndSay(n):
    def count_idx(s):
        result = []
        count = 1
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                count += 1
            else:
                result.append(str(count))
                result.append(s[i - 1])
                count = 1
        result.append(str(count))
        result.append(s[-1])
        return "".join(result)

    s = "1"
    for _ in range(2, n + 1):
        s = count_idx(s)
    return s
                

C++ Implementation:

#include 
using namespace std;

class Solution {
public:
    string countAndSay(int n) {
        string s = "1"; // Start with the first term
        for (int i = 2; i <= n; ++i) {
            s = countIdx(s); // Generate the next term
        }
        return s;
    }

    // Helper function to generate the next term based on the current term
    string countIdx(const string& s) {
        string result;
        char c = s[0];
        int count = 1;

        for (int i = 1; i < s.length(); ++i) {
            if (s[i] == c) {
                count++; // Increment count if the current character matches
            } else {
                result += to_string(count) + c; // Append count and character
                c = s[i]; // Update to the next character
                count = 1; // Reset count
            }
        }
        result += to_string(count) + c; // Append the last group
        return result;
    }
};