Look and Say (Count and Say) Sequence

Day 10

Find the nth term in Count and Say Sequence. The Count and Say sequence is the sequence of below integers:

"1"
"11"
"21"
"1211"
"111221"
"312211"
"13112221"
"1113213211"
"31131211131221"
"13211311123113112211"
"11131221133112132113212221"
"3113112221232112111312211312113211"
"1321132132111213122112311311222113111221131221"
"11131221131211131231121113112221121321132132211331222113112211"
"311311222113111231131112132112311321322112111312211312111322212311322113212221"

For example:

  • If you have “1”, the next line is “11”.
  • If you have “11”, the next line is “21”.
  • If you have “111”, the next line is “31”.
  • If you have “1111”, the next line is “41”.

See the basic pattern? Just do that for every set of repeating characters on the previous line.
Here’s what it looks like with more than one sequence:

  • If you have “11222”, the next line is “2132” (“11” becomes “21” and “222” becomes “32”).
  • If you have “112225”, the next line is “213215” (“11” becomes “21”, “222” becomes “32”, and “5” becomes “15”).

Solution

Java Program

public class Solution {
    public String countAndSay(int n) {
        if(n == 1)
            return "1";
        
        StringBuilder curr = new StringBuilder("1");
        StringBuilder prev;
        
        for(int i=1;i<n;i++)
        {
            prev = curr;
            curr = new StringBuilder();
            int count = 1;
            char say = prev.charAt(0);
            for(int j=1,len=prev.length();j<len;j++)
            {
                if(say != prev.charAt(j))
                {
                    curr.append(count).append(say);
                    count = 1;
                    say = prev.charAt(j);
                }
                else 
                    count++;
            }
            
            curr.append(count).append(say);
        }
        return curr.toString();
    }
}

Time Complexity : O(n * m)

Space Complexity : O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s