38. Count And Say¶

Difficulty: Medium

38. Count and Say

Medium

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 n^th 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?

Solution¶

class Solution {
    public String countAndSay(int n) {
        StringBuilder res = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i == 1) res.append("1");
            else {
                String current = res.toString();
                res = new StringBuilder();
                res.append(findRLE(current));
            }
        }
        return res.toString();
    }
    private String findRLE(String s) {
        int n = s.length();
        StringBuilder res = new StringBuilder();
        char prev = s.charAt(0);
        int count = 1;
        for (int i = 1; i < n; i++) {
            char current = s.charAt(i);
            if (current == prev) count++;
            else {
                res.append(count);
                res.append(prev);
                count = 1;
                prev = current;
            }
        }
        if (count > 0) {
            res.append(count);
            res.append(prev);
        }
        return res.toString();
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here