Last updated on January 19th, 2025 at 05:46 pm
Here, we see a Count and Say LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
String
Companies
Level of Question
Medium
Count and Say LeetCode Solution
Table of Contents
1. 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 way you would “say” the digit string fromcountAndSay(n-1), which is then converted into a different digit string.
To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.
For example, the saying and conversion for digit string "3322251":
Given a positive integer n, return the nth term of the count-and-say sequence.
Example 1:
Input: n = 1
Output: "1"
Explanation: This is the base case.
Example 2:
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
2. Coding Pattern Used in Solution
The provided code implements the “Count and Say” sequence generation. This pattern involves iteratively transforming a string based on specific rules, which is the core logic of the “Count and Say” problem.
3. Code Implementation in Different Languages
3.1 Count and Say C++
class Solution {
public:
string countAndSay(int n) {
if(n == 1)
return "1";
if(n == 2)
return "11";
string str = "11";
for(int i = 3; i <= n; i++)
{
str += '$';
int len = str.length();
int cnt = 1;
string tmp = "";
for(int j = 1; j < len; j++)
{
if(str[j] != str[j - 1])
{
tmp += cnt + '0';
tmp += str[j - 1];
cnt = 1;
}
else
cnt++;
}
str = tmp;
}
return str;
}
};
3.2 Count and Say Java
class Solution {
public String countAndSay(int n) {
String s = "1";
for(int i = 1; i < n; i++){
s = countIdx(s);
}
return s;
}
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++;
}
else
{
sb.append(count);
sb.append(c);
c = s.charAt(i);
count = 1;
}
}
sb.append(count);
sb.append(c);
return sb.toString();
}
}
3.3 Count and Say JavaScript
var countAndSay = function(n) {
var str = '1';
for (var i=1; i < n; i++) {
var strArray = str.split('');
str ='';
var count = 1;
// Loop through current nth level line
for (var j=0; j < strArray.length; j++) {
// Next digit is different
if (strArray[j] !== strArray[j+1]) {
// Go to next non-matching digit
str += count + strArray[j];
count = 1;
}
else {
count++;
}
}
}
return str;
};
3.4 Count and Say Python
class Solution(object):
def countAndSay(self, n):
s = '1'
for _ in range(n - 1):
s = re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1), s)
return s
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(2n) | O(2n) |
| Java | O(2n) | O(2n) |
| JavaScript | O(2n) | O(2n) |
| Python | O(2n) | O(2n) |
- The exponential growth in time and space complexity is due to the doubling of the string length with each iteration.
- While the implementation is straightforward, it is not efficient for large values of
ndue to the rapid growth of the string size. - The Python implementation uses a regular expression for string transformation, which is a concise but computationally expensive approach.