38. Count and Say LeetCode Solution

In this guide we will provide 38. Count and Say LeetCode Solution with best time and space complexity. The solution to Count and Say problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Count and Say solution in C++
Count and Say soution in Java
Count and Say solution Python
Additional Resources

38. Count and Say LeetCode Solution image

Problem Statement of Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = “1”
countAndSay(n) is the run-length encoding of countAndSay(n – 1).

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string “3322251” we replace “33” with “23”, replace “222” with “32”, replace “5” with “15” and replace “1” with “11”. Thus the compressed string becomes “23321511”.
Given a positive integer n, return the nth element of the count-and-say sequence.

Example 1:

Input: n = 4
Output: “1211”
Explanation:

countAndSay(1) = “1”
countAndSay(2) = RLE of “1” = “11”
countAndSay(3) = RLE of “11” = “21”
countAndSay(4) = RLE of “21” = “1211”

Example 2:

Input: n = 1
Output: “1”
Explanation:
This is the base case.

Constraints:

1 <= n <= 30

Follow up: Could you solve it iteratively?

Complexity Analysis

Time Complexity: O(|\texttt{ans}|)
Space Complexity: O(|\texttt{ans}|)

38. Count and Say LeetCode Solution in C++

class Solution {
 public:
  string countAndSay(int n) {
    string ans = "1";

    while (--n > 0) {
      string next;
      for (int i = 0; i < ans.length(); ++i) {
        int count = 1;
        while (i + 1 < ans.length() && ans[i] == ans[i + 1]) {
          ++count;
          ++i;
        }
        next += to_string(count) + ans[i];
      }
      ans = std::move(next);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

38. Count and Say LeetCode Solution in Java

class Solution {
  public String countAndSay(int n) {
    StringBuilder sb = new StringBuilder("1");

    while (--n > 0) {
      StringBuilder next = new StringBuilder();
      for (int i = 0; i < sb.length(); ++i) {
        int count = 1;
        while (i + 1 < sb.length() && sb.charAt(i) == sb.charAt(i + 1)) {
          ++count;
          ++i;
        }
        next.append(count).append(sb.charAt(i));
      }
      sb = next;
    }

    return sb.toString();
  }
}
// code provided by PROGIEZ

38. Count and Say LeetCode Solution in Python

class Solution:
  def countAndSay(self, n: int) -> str:
    ans = '1'

    for _ in range(n - 1):
      nxt = ''
      i = 0
      while i < len(ans):
        count = 1
        while i + 1 < len(ans) and ans[i] == ans[i + 1]:
          count += 1
          i += 1
        nxt += str(count) + ans[i]
        i += 1
      ans = nxt

    return ans
 #code by PROGIEZ