# Solution For Count And Say

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 from countAndSay(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 groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, followed by the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

Example:

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”

Approach: We can solve this problem by applying a recursive approach. We can start from n=1 and keep returning the resulting string by applying the rule of the count-and-say sequence. For a given n, we can recursively call the function to calculate the string countAndSay(n-1) which is given. To get the required string countAndSay(n), we can apply the following steps:

1. Initialize the resulting string as an empty string.
2. Initialize count as 1 and the starting character as the first character in countAndSay(n-1).
3. Traverse the string countAndSay(n-1) from the second character to the end.
4. If the current character is the same as the previous character, increment the count.
5. If the current character is different from the previous character, append the count and the previous character to the resulting string and start a new count for the current character.
6. After the traversal is complete, append the last count and character to the resulting string and return the resulting string.

For example, consider the following code for the countAndSay function:

“`python
def countAndSay(n: int) -> str:
if n == 1:
return “1”

``````res = ""
prev = countAndSay(n-1)
count = 1
prev_char = prev

for i in range(1, len(prev)):
if prev[i] == prev_char:
count += 1
else:
res += str(count) + prev_char
count = 1
prev_char = prev[i]

res += str(count) + prev_char

return res
``````

“`

Time Complexity: Each recursive call performs a linear traversal of the previous string, so the time complexity of the countAndSay function is O(n*m), where n is the input value of n, and m is the length of the previous string. In the worst case, m = 2^(n-1) which is the length of the maximum possible string.

Space Complexity: Each recursive call requires a new string of length at most 2^(n-1). Therefore, the space complexity of the countAndSay function is O(2^n).

## Step by Step Implementation For Count And Say

```public class Solution {
public String countAndSay(int n) {
// Base case
if (n == 1) {
return "1";
}

// Recursive case
String prev = countAndSay(n - 1);
StringBuilder sb = new StringBuilder();

// Iterate through the previous result string
for (int i = 0; i < prev.length(); i++) {
// Keep track of the number of consecutive occurrences
int count = 1;

// Check for consecutive occurrences
while (i < prev.length() - 1 && prev.charAt(i) == prev.charAt(i + 1)) {
count++;
i++;
}

// Append the number of occurrences and the character to the string builder
sb.append(count);
sb.append(prev.charAt(i));
}

// Convert the string builder to a string and return
return sb.toString();
}
}```
```def countAndSay(n):

if n == 1:

return "1" # Base case

prev = countAndSay(n-1) # Recursive call

count = 1 # Initialize count

i = 1

res = "" # Initialize result

while i < len(prev):

if prev[i] == prev[i-1]:

count += 1

else:

# Append count and character

res += str(count)

res += prev[i-1]

count = 1

i += 1

# If last character is same as

# previous one

if prev[i-1] == prev[i-2]:

res += str(count)

res += prev[i-1]

return res```
```var countAndSay = function(n) {
};```
```int countAndSay(int n)
{
// Base cases
if (n == 1)      return "1";
if (n == 2)      return "11";

// Find n'th term by generating all terms from 3 to
// n-1.  Every term is generated using previous term
string str = "11"; // Initialize previous term
for (int i = 3; i<=n; i++)
{
// In below for loop, previous character is processed in
// current iteration. That is why a dummy character is
// added to make sure that loop runs one extra iteration.
str += '\$';
int len = str.length();

int cnt = 1; // Initialize count of matching chars
string tmp = ""; // Initialize i'th term in series

// Process previous term to find the next term
for (int j = 1; j < len; j++)
{
// If current character does't match
if (str[j] != str[j-1])
{
// Append count of str[j-1] to temp
tmp += cnt + '0';

// Append str[j-1]
tmp += str[j-1];

// Reset count
cnt = 1;
}

//  If matches, then increment count of matching
// characters
else cnt++;
}

// Update str
str = tmp;
}

return str;
}```
```public class Solution {
public string CountAndSay(int n) {
// Base case
if (n == 1) {
return "1";
}

// Use previous result to generate next result
string prevResult = CountAndSay(n - 1);
return GenerateNextResult(prevResult);
}

private string GenerateNextResult(string prevResult) {
// Track current number and count
char currNum = prevResult;
int currCount = 1;

// Use StringBuilder to efficiently create result string
StringBuilder result = new StringBuilder();

// Iterate through previous result string
for (int i = 1; i < prevResult.Length; i++) {
// If current number is different than previous number
if (prevResult[i] != currNum) {
// Append current number and count to result
result.Append(currCount);
result.Append(currNum);

// Reset current number and count
currNum = prevResult[i];
currCount = 1;
}
// Otherwise, increment count
else {
currCount++;
}
}

// Append last number and count to result
result.Append(currCount);
result.Append(currNum);

return result.ToString();
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]