Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 18

Description

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:

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

Example 2:

Constraints:

• 1 <= n <= 30

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();

class Solution {
  string solve(int n) {
    if(n == 1) return "1";
    string prev = solve(n - 1);
    string result = "";
    char current = prev.front();
    int count = 0;
    for(auto c : prev) {
      if(current == c) {
        count += 1;
      } else {
        result += to_string(count) + current;
        current = c;
        count = 1;
      }
    }
    result += to_string(count) + current;
    return result;
  }
public:
  string countAndSay(int n) {
    return solve(n);
  }
};

// Accepted
// 30/30 cases passed (21 ms)
// Your runtime beats 37.31 % of cpp submissions
// Your memory usage beats 42.61 % of cpp submissions (6.7 MB)