7. Count and Say

7. Count and Say

Problem link :- click here

package programs;

public class String__7
{

	/*
		1 -->		1
		2-->		11
		3-->		2   1
		4-->		12 11
		5-->		11 12 21
		6-->		31 22 11
		7-->		13 11 22 21
		8-->		11 13 21 32 11
		9-->		31 13 12 11 13 12 21
		10->		13 21 13 11 12 31 13 11 22 11
		
		its like if there is      111         then we say it as "triple one" but
		here we will write it as     31
		
		we are creating a recursive method because if we want the "countAndSay(n)"
		then we need the "countAndSay(n-1)"
		
		after taking the string from "countAndSay(n-1)" we will iterate through the string 
			while iterating we will take the first char and find 
			how many times it is repeated ?
			and we append the result with count(no. of times char as repeated)
			and that char
			
			then we will update the char that we are holding and update the count.
	*/
	
	static StringBuffer countAndSay(int n)
	{
		if(n<=0)
			return new StringBuffer("0");
		else if(n == 1)
			return new StringBuffer("1");
		
		StringBuffer s = countAndSay(n-1);
		
		StringBuffer result = new StringBuffer(); // output
		Character temp = s.charAt(0);		          //  first char
		int count = 1;					        //  no. of times repeated continuously
		
		for(int i=1; i<s.length(); i++)
		{
			if( s.charAt(i) == temp )
				count++;
			else
			{
				//appending the number of times the char repeated continuously
				// and that      char (which has repeated)
				result.append( count );
				result.append( temp );
				
				//updating the temp and the count
				temp = s.charAt(i);
				count = 1;
				//count equal to one because control has come to else
				//because this is a new char (which is pointed by 'i' right now)
			}
		}
		result.append( count );
		result.append( temp );
		
		return result;
	}
	
	public static void main(String[] args)
	{
		StringBuffer s = countAndSay(6);
		
		System.out.println("Output is : " + s);
	}

}

Time complexity :- O()
Space complexity :- O()