Count and Say easy
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 ofcountAndSay(n - 1)
Run-length encoding (RLE) replaces consecutive identical characters with the count followed by the character. For example, "3322251" is encoded as "23321511" (two 3s, two 2s, one 5, one 1).
Given a positive integer n, return the n-th element of the count-and-say sequence.
Examples
> Case 1:
Input: n = 1
Output: "1"
> Case 2:
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = "11" (one 1)
countAndSay(3) = "21" (two 1s)
countAndSay(4) = "1211" (one 2, one 1)Constraints
- 1 to 30 inclusive (
1 <= n <= 30)
How the Sequence Grows
Building the count-and-say sequence
Step 1 of 6
1
[0]n=1: "1". Read it aloud: "one 1".
Approach: Iterative String Building
Build each term from the previous one by scanning for runs of identical characters.
Explanation
- Start with
"1"(base case) - For each subsequent term, scan the current string for groups of consecutive identical characters
- For each group, append the count and the character to build the next string
- Use a list/StringBuilder to build efficiently (avoid O(n^2) string concatenation)
Run-Length Encoding (RLE) is a real compression technique used in formats like BMP images and fax transmissions. It works best on data with many consecutive repeated values. This problem is a direct application of RLE.
Analysis
- Time Complexity:
O(n * L)where L is the length of the sequence at step n (grows roughly exponentially but is bounded for n up to 30) - Space Complexity:
O(L)for the current and next strings