38. Count and Say

Hello, reader 👋🏽 ! Welcome to day 18 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 38. Count and Say .

🤔 Problem Statement

Count and Say is a recursive algorithm that does the following:
- countAndSay(1) = 1
- countAndSay(n) is the way n-1 digits are said which is then converted to a different string.
E.g.:
- countAndSay(3) => countAndSay(2) => countAndSay(1)
  - countAndSay(1) = 1
  - countAndSay(2) = one 1 => 11
  - countAndSay(3) = two 1s => 21
  - Output: 21
- countAndSay(4) => countAndSay(3)
  - Output: 1211

💬 ## Thought Process - Recursion

I don't know why this question has so many dislikes. Probably because it's basically you won't get such a question anywhere.
But then this was a great way to practice and come up with recursive solutions.
Immediately looking into the question, you can figure out this has to do with recursion because not only does it have a pattern of a problem solved from previous ones, it's also clearly mentioned with base cases!
So let's look into how we can come up with some kind of recurrence.
For all n except for 1, notice how first it needs to be mapped to something else to get the solution for that n.
E.g. for countAndSay(2), you will get 1 as the previous sub problem answer => countAndSay(1).
Now instead of returning just 1, we will have to map this value to the frequency(1) + "1". So 1 becomes 11.
This is exactly what we will do. When we get a value returned from countAndSay(n-1) to countAndSay(n), we will map the returned value to each of the number's frequency. Then return it.
Let's look into the code now.

👩🏽‍💻 Solution - Recursion

Below is the code for the recursive algorithm for the above problem:

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

      String prevCount = countAndSay(n-1);
      String currentSay = say(prevCount);

      return currentSay;
  }

  private String say(String s) {
      char[] countArr = s.toCharArray();
      int count = 1;
      char prev = countArr[0];
      int n = countArr.length;

      StringBuilder sb = new StringBuilder();
      for(int i = 1; i<=n; i++) {
          if(i == n) {
              sb.append(count + "" + prev);
              break;
          }
          char ch = countArr[i];
          if(ch == prev) {
              count++;
          }
          else {
              // add the count and num to the sb
              sb.append(count + "" + prev);
              prev = ch;
              count = 1;
          }
      }

      return sb.toString();
  }
}

Time Complexity: O(n*k)
  - k = length string returned from countAndSay(n-1)
Space Complexity: O(n*k)
  - l = length string returned from countAndSay(n-1)
  - n = implicit stack space

You can find the code for this problem on GitHub repo: 38. Count and Say.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

38. Count and Say

Problem Solving - Day 18

Table of contents

🤔 Problem Statement

👩🏽‍💻 Solution - Recursion

Conclusion