def countAndSay(n):
    result = '1'
    for _ in range(n - 1):
        count, last = 0, None
        newString = ''

        for digit in result:
            if last is None or digit == last:
                count += 1
                last = digit
            else:
                newString += str(count) + last
                last = digit
                count = 1
        
        newString += str(count) + last
        result = newString
    
    return result

# Time: O(2 ^ n) because the sequence at worst double during each iteration
# Space: O(2 ^ n)
def countAndSay2 (n):
    sequence = [1]
    for _ in range(n - 1):
        next = []
        for digit in sequence:
            if not next or next[-1] != digit:
                next += [1, digit]
            else:
                next[-2] = next[-2] + 1
        sequence = next
    
    return ''.join(map(str, sequence))
