[LeetCode] 38. Count and Say

Table of Contents

Description

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.

Approach

Use recursion to generate each term of the sequence based on the previous one, applying a run-length encoding process to describe consecutive digits. The approach efficiently builds each new string by counting and grouping identical digits from the prior result, following the rules of the count-and-say sequence.

Solution

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function (n) {
  // Base case: when n is 1, return the string "1"
  if (n === 1) return n.toString();

  // Recursively get the previous sequence string
  const s = countAndSay(n - 1);
  let result = "";

  // 'count' keeps track of the number of consecutive identical digits, start with 1
  for (let i = 0, count = 1; i < s.length; i++) {
    const num = s[i];
    const nextNum = s[i + 1];

    if (num === nextNum) {
      // If current and next characters are the same, increment count
      count++;
    } else {
      // If different, the consecutive sequence ends,
      // append count and the digit to the result string
      result += `${count}${num}`;
      // Reset count for the next sequence
      count = 1;
    }
  }

  return result;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n \times m)$, where $n$ is the input number and $m$ is the length of the string at each step. For each term, every character of the previous string is processed, and this is repeated for $n$ terms.

Space Complexity

The space complexity is $O(n \times m)$, where $n$ is the input number and $m$ is the length of the string at each step. This is because each recursive call holds a string of length $m$ on the call stack, leading to $n$ layers in the worst case.