Заблуждения программистов о трудоустройстве

Но ведь амортизационная стоимость и вправду будет О(n)

Выпуск#21: ITренировка — актуальные вопросы и задачи от ведущих компаний

Решение на питоне динамикой за О(длина строки)

Заголовок спойлера

def fbi(s):
    d = [1] * len(s)
    if s[1] != '0' and int(s[:2]) <= 26:
        d[1] = 2
    for i in range(2, len(s)):
        if s[i] == '0':
            d[i] = d[i - 2]
            continue
        d[i] = d[i - 1]
        if s[i - 1] != '0' and int(s[i - 1:i + 1]) <= 26:
            if int(s[i - 2:i]) <= 26:
                d[i] += d[i - 2]
            else:
                d[i] += d[i - 1]
    return d[-1]

Адский проект

Рискну предположить, что имелся в виду grpc