Solution by rohitnandi12


  • 0
    R

    Primary Thougths
    This is direct implementation problem no hidden logic. Simplest form of Dynamic Programming
    where you save the previous result to compute the next result.

    Test Cases

    Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

    Test Inputs
    T1 : 1      // output : "1"
    T2 : 10     // output : "13211311123113112211"
    T2 : x<=0   // output : "1"
    
    

    Approach #1 Dynamic Programming

    Java

    class Solution {
        public String countAndSay(int n) {
    
            StringBuilder last = new StringBuilder("1");
            n--;
            StringBuilder next = null;
    
            int count=0;
    
            while(n-->0){
                next = new StringBuilder();
                count = 1;
                int i=0;
                for(;i<last.length()-1;i++){
    
                    if(last.charAt(i)==last.charAt(i+1))
                        count++;
                    else{
                        next.append(count);
                        next.append(last.charAt(i));
                        count = 1;
                    }
                }
                if(i==0 || last.charAt(i)!=last.charAt(i-1)){
                    count = 1;
                }
                next.append(count);
                next.append(last.charAt(i));
    
                last = next;
            }
    
            return last.toString();
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    • Space complexity : $$O(1)$$.

    Thank You. Happy Coding :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.