Count And Say Problem Solution

Count And Say Problem: 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 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.

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"

Count And Say Problem Solution

Problem Solution In Python

class Solution(object):
    def countAndSay(self, n):
        s0 = '1'
        for i in range(1, n):
            s1, k = '', 1
            for j in range(1, len(s0)):
                if s0[j-1] == s0[j]: k += 1
                else: s1, k = s1 + str(k) + s0[j-1], 1
            s1 += str(k) + s0[-1]
            s0 = s1
        return s0

Problem Solution In Java

public String countAndSay(int n) {
    if(n == 0) return "";
    String res = "1";
   for(int i = 1; i <n; i++){
       String s = res;  res="";  
       int count = 1;// attention for the logic
       char pre = s.charAt(0);
       for(int j = 1; j < s.length(); j++){
            if(s.charAt(j) == pre)
                count++;
            else{
                res += count+""+pre;
                pre = s.charAt(j);
                count = 1;
            }
      }
      res += count +""+ pre;
   }
   return String.valueOf(res);
}

Problem Solution In C++

class Solution {
public:
    string countAndSay(int n) {
        string temp="1";
        string ans="";
        if(n==1)return temp;
        for(int i=2;i<=n;i++)
        {
            char value=temp[0];
            int count=1;
            ans="";
            for(int j=1;j<temp.size();j++)
            {
                if(temp[j]==value)count++;
                else 
                {
                    ans+=count+'0';
                    ans+=value;
                    count=1;
                    value=temp[j];
                }
            }
            ans+=count+'0';
            ans+=value;
            temp=ans;
        }
        return ans;
    }
};

Problem Solution In C

char* fromLast(char* last) {
    char *s = last;
    int count;
    int index = 0;
    char *result = (char*) malloc(2 * strlen(last));
    while(*s != '\0') { 
        count = 1;
        while(*s == *(s+1)) {   
            count++;
            s++;
        }
        result[index++] = count + '0';
        result[index++] = *(s);
        s++;
    }
    result[index] = '\0';
    return result;
}
char* countAndSay(int n) {
    if(n == 1) 
        return "1";
    return fromLast(countAndSay(n-1));
}