CountandSay38.java

/*
 * Problem: LeetCode 38 - Count and Say
 *
 * Problem Statement:
 * The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
 * countAndSay(1) = "1", and countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1).
 * To determine how you "say" a digit string, split it into the minimal number of groups so that 
 * each group is a contiguous section of the same digit, then say the number of digits, then the digit.
 *
 * Intuition:
 * This problem is a classic application of Run-Length Encoding (RLE). Each term is generated by 
 * scanning the previous term and counting consecutive occurrences of the same character.
 *
 * Approach:
 * 1. Use recursion to reach the base case (n=1 returns "1").
 * 2. For any n > 1, retrieve the string for (n-1).
 * 3. Iterate through the (n-1) string using a single pointer, maintaining a counter for identical consecutive digits.
 * 4. When the digit changes, append the count and the digit to a StringBuilder.
 * 5. Append the final group after the loop finishes and return the result.
 *
 * Time Complexity: O(2^n) in the worst case, though practically bounded by the growth of the sequence. 
 * The length of the sequence grows at a rate of approximately 1.303 (Conway's constant).
 * Space Complexity: O(M) where M is the length of the resulting string, plus O(n) for the recursion stack.
 *
 * Edge Cases:
 * - n = 1: Handled by the base case.
 *
 * Dry Run (n = 4):
 * - n=1: returns "1"
 * - n=2: previous="1". Loop i=1 to 0 (skipped). Append count(1) + char('1') -> "11"
 * - n=3: previous="11". i=1: '1'=='1', count=2. Append count(2) + char('1') -> "21"
 * - n=4: previous="21". i=1: '1'!='2', append count(1) + char('2'), count=1. Append count(1) + char('1') -> "1211"
 *
 * Correctness Check:
 * The solution correctly implements the recursive definition and handles the final group of digits 
 * that the loop logic would otherwise miss.
 */
public class CountandSay38 {
    public String countAndSay(int n) {
        // Base case: The sequence starts with "1"
        if (n == 1) {
            return "1";
        }
        
        // Recursive step: We need the (n-1)th string to calculate the nth string
        String previous = countAndSay(n - 1);
        StringBuilder sb = new StringBuilder();
        
        // Initialize count to 1 for the first character of the current run
        int count = 1;
        
        // Iterate through the string starting from the second character
        for (int i = 1; i < previous.length(); i++) {
            // If current character matches the previous one, increment the run length
            if (previous.charAt(i) == previous.charAt(i - 1)) {
                count++;
            } else {
                // If character changes, "say" the previous run: [count][digit]
                sb.append(count).append(previous.charAt(i - 1));
                // Reset count for the new character run
                count = 1;
            }
        }
        
        // The loop finishes before the last group is appended. 
        // We must append the count and the value of the final character group.
        sb.append(count).append(previous.charAt(previous.length() - 1));
        
        return sb.toString();
    }
}