Count and Say Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook JPMorgan
StringViews 8383

Problem Statement

The Count and Say LeetCode Solution – “Count and Say” asks you to find the nth term of the count-and-say sequence.

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 find out how we’ll “say” a digit string, first split the string into a minimum number of groups of consecutive characters. Now, for each group, first, display the number of characters and then the character.

Example:

Input:  n = 1
Output: "1"

Explanation:

  • n = 1 is the base case of the recursion, hence answer is 1.
Input:  n = "4"
Output: "1211"

Explanation:

  • CountAndSay(1) = “1”.
  • CountAnd Say(2) = say “1” = one time 1 = “11”.
  • CountAnd Say(3) = say “11” = two times 1 = “21”.
  • CountAndSay(4) = say “21” = one time 2 and one time 1 = “1211”.

Approach

Idea:

  1. The main idea to solve this problem is to use Recursion.
  2. This problem can also be solved efficiently using the iterative method, picking each time the previous string and working upon the string to get the current answer.
  3. Also, we need a mapping of integers to strings.
  4. For finding the answer to the nth sequence, consider the string obtained in the previous sequence.
  5. Iterate for the string and find the count of consecutive same characters and the type of character.
  6. Use the map to find the current answer.

Code

Count and Say Leetcode C++ Solution:

class Solution {
public:
    string countAndSay(int n) {
        vector<string> dp(n+1);
        dp[1] = "1";
        vector<string> conv = {"","1","2","3","4","5","6","7","8","9"};
        for(int i=2;i<=n;i++){
            int cnt = 1;
            for(int j=1;j<dp[i-1].length();j++){
                if(dp[i-1][j]==dp[i-1][j-1]){
                    cnt++;
                }
                else{
                    dp[i] += conv[cnt];
                    dp[i] += dp[i-1][j-1];
                    cnt = 1;
                }
            }
            dp[i] += conv[cnt];
            dp[i] += dp[i-1].back();
        }
        return dp.back();
    }
};

Count and Say Leetcode Java Solution:

class Solution {
    public String Count(String s){
        int cnt = 1;
        char ch = s.charAt(0);
        StringBuilder curr = new StringBuilder();
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==ch){
                cnt++;
            }
            else{
                curr.append(cnt);
                curr.append(ch);
                ch = s.charAt(i);
                cnt = 1;
            }
        }
        curr.append(cnt);
        curr.append(ch);
        return curr.toString();
    }
    public String countAndSay(int n) {
        String s = "1";
        for(int i=1;i<n;i++){
            s = Count(s);
        }
        return s;
    }
}

Complexity Analysis for Count and Say Leetcode Solution

Time Complexity

The time complexity of the above code is O(N*L), where N = nth term in the sequence and L = max length of the string.

Since we traverse n times and each time we’ll iterate for the maximum length of string L, hence time complexity is O(N*L).

Space Complexity

The space complexity of the above code is O(N). We’re using a linear vector of size N to store all answers.

Reference: https://en.wikipedia.org/wiki/Recurrence_relation

Translate »