Given an integer n, generate the nth count and say sequence I am solving interview questions from here.


  Problem : Given an integer n, generate the nth count and say sequence. 
  The count-and-say sequence is the sequence of integers beginning as follows:  1, 11, 21, 1211, 111221, ...
  
  1 is read off as one 1 or 11.
  
  11 is read off as two 1s or 21.
  
  21 is read off as one 2, then one 1 or 1211.
  
  Note : The sequence of integers will be represented as a string.
  
  Example: if n = 2, the sequence is 11.


How should I further optimize my solution?

def count_and_say(num):
        string = '11'
        cnt = 0
        new_string = []
        if num == 1:
            return "1"
        while num != 2:
            cnt += 1
            for i in range(len(string)):
                if i+1 != len(string):
                    if string[i] == string[i+1]:
                        cnt += 1
                    else:
                        new_string.append(str(cnt)+string[i])
                        cnt = 1
                else:
                    new_string.append(str(cnt)+string[i])
            cnt = 0
            num -= 1
            string = ''.join(new_string)
            new_string = []
        return string
In each step of the "count-and-say sequence" (which is more usually called the "look-and-say sequence") you have to find the groups of consecutive runs of identical digits. So if you have the value 111221, these groups are 111, 22, and 1. Python has a built-in function itertools.groupby for finding groups in an iterator, and using this function, the look-and-say step becomes:

new_value = ''
for digit, group in groupby(value):
    count = sum(1 for _ in group)
    new_value += str(count) + digit
value = new_value


which can be rearranged into a single expression:

value = ''.join(str(sum(1 for _ in group)) + digit
                for digit, group in groupby(value))


and so the whole sequence can be generated like this:

from itertools import groupby

def look_and_say(value='1'):
    "Generate the look-and-say sequence starting at value."
    while True:
        yield value
        value = ''.join(str(sum(1 for _ in group)) + digit
                        for digit, group in groupby(value))


To select only the \$n\$th value of the sequence, use itertools.islice:

next(islice(look_and_say(), n - 1, None))