Count And Say Editorial

Practice Problem Link: Count And Say | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Count-And-Say is a sequence of numbers given below:

• 1
• 11
• 21
• 1211
• 111221

This sequence starts with 1. 

1 is read as one 1 -> 11 

11 is read as two 1 -> 21

 21 is read as one 2, one 1 -> 1211 

1211 is read as one 1, one 2, two 1 -> 111221

And so on…

GIven a number n, find the n^th sequence.

Approach

The approach to this problem is straightforward and simple.

• The n^th sequence will be generated from the (n - 1)^th sequence and the (n - 1)^th sequence will be generated from the (n - 2)^th sequence and so on till n = 1.
• Eventually, all the sequences from n to 1 will be generated recursively.
• For n = 1, return the sequence “1”.  
• To generate the i^th sequence from its previous sequence traverse the previous sequence and keep the count of the consecutive element. As soon as two different elements are encountered or the end of the sequence is reached. First, add the count of the element in the current sequence and then the corresponding element.

Analysis

• Time Complexity: O(n²)
• Auxiliary Space Complexity: O(n²)

Implementation

C++

string countAndSay (int n) {
   if(n==1) {
       return "1";
   }
   string previousTerm = countAndSay(n - 1);
   int count = 0;
   char prev = '0';
   string ans = "";
   for(int i = 0; i < previousTerm.size(); i++) {
       if (previousTerm[i] == prev) {
           count++;
       } else {
           if (count != 0) {
               ans += count + '0';
               ans += prev;
           } 
           prev = previousTerm[i];
           count = 1;
       }
   }
   if (count != 0) {
       ans += count + '0';
       ans += prev;
   }
   return ans;
}

Java

class Solution {
   String countAndSay (int n) {
       if(n==1) {
           return "1";
       }
       String previousTerm = countAndSay(n - 1); 
       int count = 0;
       char prev = '0';
       String ans = "";
       for(int i = 0; i < previousTerm.length(); i++) {
           if (previousTerm.charAt(i) == prev) {
               count++;
           } else {
               if (count != 0) {
                   ans += count + 0;
                   ans += prev;
               } 
               prev = previousTerm.charAt(i);
               count = 1;
           }
       }
       if (count != 0) {
           ans += count + 0;
           ans += prev;
       }
       return ans;
   }
}