Explorer
Data Structures & Algorithms

Generate the n-th term of the count-and-say sequence.

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 run-length encoding of `countAndSay(n - 1)`.

Examples

Input: n = 1

Output: "1"

Explanation: Combining the input according to Count and say logic yields "1".

Input: n = 4

Output: "1211"

Explanation: Combining the input according to Count and say logic yields "1211".

Complexity

Time Complexity: O(2^N)

Space Complexity: O(2^N)

Hints

šŸ’” Hint 1: Base case: countAndSay(1) = "1". šŸ’” Hint 2: For each step from 2 to n, apply run-length encoding on the previous string. šŸ’” Hint 3: Count contiguous identical digits and append count + digit to form the next string.

Editorial & Approach

Problem Overview & Intuition

Iteratively construct the sequence starting from "1". For each transition, run-length encode consecutive identical digits into [count, digit], producing the next term in the sequence.

Step-by-Step Approach

  1. Initialize curr = "1".
  2. Iterate i from 2 to n.
  3. Traverse curr using two pointers or a loop counting contiguous duplicate characters.
  4. Append count + char to next.
  5. Update curr = next.
  6. Return curr.

Optimal Implementation (JavaScript)

function countAndSay(n) {
  let curr = '1';
  for (let i = 2; i <= n; i++) {
    let next = '', j = 0;
    while (j < curr.length) {
      let count = 1;
      while (j + 1 < curr.length && curr[j] === curr[j + 1]) {
        count++;
        j++;
      }
      next += count + curr[j];
      j++;
    }
    curr = next;
  }
  return curr;
}

Complexity Analysis

Time Complexity O(2^N) ā€” sequence length approximately grows by factor of 1.3 per step.
Space Complexity O(2^N) ā€” storage for the string.

Edge Cases & Corner Traps Handled

  • n = 1: returns "1".
  • n = 2: returns "11".
  • n = 4: returns "1211".

Count and say

Hard
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)`.
Example Scenarios
1Example 1
Input: n = 1
Output: "1"
Explanation:

Combining the input according to Count and say logic yields "1".

2Example 2
Input: n = 4
Output: "1211"
Explanation:

Combining the input according to Count and say logic yields "1211".

Editor
Loading Editor...
n =
1
Output:Click "Run" above to execute and verify your code here.
1