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 ofcountAndSay(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 nth element of the count-and-say sequence.
Examples:
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.
Constraints
countAndSay(3) = RLE of "11" = "21"
Time Complexity:
Time Complexity = O(n x m)
where m is length of the generated string at each step.
Space Complexity:
Space Complexity = O(m)
Approach
- For every iteration from 2 to n:
- Initialize an empty string
rleto store the next sequence. - Traverse the current string curr and keep a count of
repeating characters. - If the
current characteris the same as the previous one, increment the count. - Otherwise:
Append the countand the previous character to rle.- Reset
count to 1for the new character.
- Initialize an empty string
- After the
loop, update curr with the newly formedrle. - This process continues until we reach the
n-th term.
Dry Run
Input: n = 4
Initial:
curr = "1"
i = 2:
curr = "1"
rle = ""
count = 1
j = 1:
curr[1] != curr[0] (undefined != '1')
rle = "" + "1" + "1" = "11"
count = 1
curr = "11"
i = 3:
curr = "11"
rle = ""
count = 1
j = 1:
curr[1] == curr[0] ('1' == '1')
count = 2
j = 2:
curr[2] != curr[1] (undefined != '1')
rle = "" + "2" + "1" = "21"
count = 1
curr = "21"
i = 4:
curr = "21"
rle = ""
count = 1
j = 1:
curr[1] != curr[0] ('1' != '2')
rle = "" + "1" + "2" = "12"
count = 1
j = 2:
curr[2] != curr[1] (undefined != '1')
rle = "12" + "1" + "1" = "1211"
count = 1
curr = "1211"
Final:
return "1211"
Output: "1211"
var countAndSay = function(n) {
let curr = "1";
for(let i = 2; i <= n; i++) {
let rle = "";
let count = 1;
for(let j = 1; j <= curr.length; j++) {
if(curr[j] === curr[j - 1]) {
++count;
}else {
rle = rle + count + curr[j - 1];
count = 1;
}
}
curr = rle;
}
return curr;
};
def countAndSay(n):
curr = "1"
for i in range(2, n + 1):
rle = ""
count = 1
for j in range(1, len(curr) + 1):
if j < len(curr) and curr[j] == curr[j - 1]:
count += 1
else:
rle += str(count) + curr[j - 1]
count = 1
curr = rle
return curr
class Solution {
public String countAndSay(int n) {
String curr = "1";
for (int i = 2; i <= n; i++) {
StringBuilder rle = new StringBuilder();
int count = 1;
for (int j = 1; j <= curr.length(); j++) {
if (j < curr.length() && curr.charAt(j) == curr.charAt(j - 1)) {
count++;
} else {
rle.append(count).append(curr.charAt(j - 1));
count = 1;
}
}
curr = rle.toString();
}
return curr;
}
}
class Solution {
public:
string countAndSay(int n) {
string curr = "1";
for (int i = 2; i <= n; i++) {
string rle = "";
int count = 1;
for (int j = 1; j <= curr.length(); j++) {
if (j < curr.length() && curr[j] == curr[j - 1]) {
count++;
} else {
rle += to_string(count) + curr[j - 1];
count = 1;
}
}
curr = rle;
}
return curr;
}
};
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* countAndSay(int n) {
char* curr = (char*)malloc(2);
strcpy(curr, "1");
for (int i = 2; i <= n; i++) {
int len = strlen(curr);
char* rle = (char*)malloc(len * 2 + 1);
int index = 0, count = 1;
for (int j = 1; j <= len; j++) {
if (j < len && curr[j] == curr[j - 1]) {
count++;
} else {
index += sprintf(rle + index, "%d%c", count, curr[j - 1]);
count = 1;
}
}
free(curr);
curr = rle;
}
return curr;
}
public class Solution {
public string CountAndSay(int n) {
string curr = "1";
for (int i = 2; i <= n; i++) {
string rle = "";
int count = 1;
for (int j = 1; j <= curr.Length; j++) {
if (j < curr.Length && curr[j] == curr[j - 1]) {
count++;
} else {
rle += count.ToString() + curr[j - 1];
count = 1;
}
}
curr = rle;
}
return curr;
}
}
