38. Count and Say

38. Count and Say

Problem Description

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.

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"

 

Constraints:

• 1 <= n <= 30

This is a sequence that has been calculated and spoken. The sequence is as follows:

1, 11, 21, 1211, 111221, ...

1 is read as a 1, so the next one becomes 11  
11 is read as 2 1s, which is 21  
21 read as 1 2 1 1, get 1211
1211 1 1, 1 2, 2 1 111221 

Idea:

I believe that many people in this question are like me. After understanding the question, they feel that it is simple. Just look at the code below.

Let`s Code It!

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    if(n <= 1) return "1";

    var countSay = '1';

    for(var i = 2 ; i <= n ; i++){
        var num = countSay.charAt(0);
        var temp = countSay;
        var count = 1;

        countSay = ''; // Empty string stored in this round


        for(var j = 1 ; j < temp.length; j++){
            // The numbers are the same, count++
            if(temp.charAt(j) == num){
                count++;
            } else {
                // If the numbers are different, add the current count and num to the string, update num, and the new num starts from 1
                countSay += count;     
                countSay += num;
                num = temp.charAt(j);
                count = 1;
            }
        }
        countSay += count;     
        countSay += num;
    }
    return countSay;
};

OR

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    let s = '1';
    
  while (n > 1) {
    let count = 0;
    let next = '';

    for (let i = 0; i <= s.length; i++) {
      if (i === s.length || (i > 0 && s[i] !== s[i - 1])) {
        next += count + s[i - 1]; // Say
        count = 0;
      }

      count++; // Count
    }

    s = next;
    n--;
  }

  return s;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #38 Count and Say

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!