# your code goes here
import time
 
from functools import wraps
from threading import Thread

import random
import string
 
def time_it(f):
    """
    run the function 100,000 times and print time
    """
    @wraps(f)
    def wrapper(*args, **kwargs):
        start_time = time.time()
        for i in range(10000): 
            r = f(*args, **kwargs)
        print(f.__name__, time.time() - start_time)
        return r
    return wrapper
    
    
@time_it
def find_max_alpha_sequence_optimal_way(source):
    answer = [source[0],]
    for l in source[1:]:
        if l >= answer[-1][-1]:
            answer[-1] += l
        else:
            answer.append(l)
    return max(answer, key=lambda x: len(x)) 
 
@time_it
def find_max_alpha_sequence(source):
    answer = [source[0],]
    for l in source[1:]:
        if l >= answer[-1][-1]:
            answer[-1] += l
        else:
            answer.append(l)
    return sorted(answer, key=lambda x: len(x))[-1]
 
@time_it
def max_alpha_sub(s):
    def split_by_alpha_order(s):
        start = 0
        for i,(a,b) in enumerate(zip(s,s[1:])):
            if a>b:
                yield s[start:i+1]
                start = i+1
        yield s[start:]
    return max(split_by_alpha_order(s),key=len)
 
@time_it
def max_alpha_sub_simple(s):
    if not s:
        return s
    
    start = 0
    max = (0,1)
    for index in range(1,len(s)+1):
        if index == len(s) or s[index-1]>s[index]:
            if index - start>max[1]-max[0]:
                max=(start,index)
            start = index
 
functions = (
    find_max_alpha_sequence,
    find_max_alpha_sequence_optimal_way,
    max_alpha_sub,
    max_alpha_sub_simple
    )
 
str = ''.join(random.choice(string.ascii_letters) for _ in range(100))
 
for f in functions:
    t = Thread(target=f, args=(str,))
    t.start()