38. Count and Say - DevCodeEx

Explanation

To solve this problem, we need to generate the nth element of the count-and-say sequence. The count-and-say sequence is a series of strings where each subsequent string is a "say what you see" version of the previous string. We start with "1" as the first element, and then describe the count of each digit in the previous string. For example, if we have "1211" as the third element, we would count the occurrences of each digit in the second element, which is "11", resulting in "21".

We can iterate through the sequence by starting with "1" and applying the run-length encoding process iteratively to generate subsequent elements. The key idea is to keep track of the current count of consecutive digits as we iterate through each previous element.

Time complexity: O(2^n), where n is the input parameter n.
Space complexity: O(2^n) to store each element in the sequence.

View Leetcode Problem

class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        
        String prev = countAndSay(n - 1);
        StringBuilder result = new StringBuilder();
        int count = 1;
        
        for (int i = 0; i < prev.length(); i++) {
            if (i + 1 < prev.length() && prev.charAt(i) == prev.charAt(i + 1)) {
                count++;
            } else {
                result.append(count).append(prev.charAt(i));
                count = 1;
            }
        }
        
        return result.toString();
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.