Hackerrank `super-functions-strings` завершается из-за тайм-аута

Question

Учитывая строку, p, состоящую из строчных букв, вычислить суммирование функции F(p) = [len(p)**distinct(p)]%[10**9 + 7] по всем возможным различным подстрокам F. Поскольку результат довольно большой, выведите его по модулю 10 ** 9 + 7.

Например, для 'aba' это:

• F (a) = 1
• F (ab) = 4
• F (aba) = 9
• F (b) = 1
• F (ba) = 4

Для которого сумма равна 19.

Вот мое решение:

import os
import sys

def superFunctionalStrings(s):
    a=list()
    thesum=0
    length = len(s) + 1
    modu=10**9 + 7
    for j in range(length):
        for i in range(j+1, length):
            b = s[j:i]
            if b not in a:
                a.append(b)
                thesum += (len(b)**len(set(b)))%(modu)
    summ = thesum%(modu)       
    return(summ)         

Что я могу сделать, чтобы оптимизировать его, чтобы тайм-аут не возник? (Я предполагаю, что внешние библиотеки не допускаются)

Answer 1

Одним из изменений, которое устранит O (n) фактор сложности, будет сделать a набор вместо списка.

Для вычисления b in a для списка требуется поиск по всему спискуO (n).Альтернативно, вычисление b in a для набора хэшируется, что занимает O (1).

Answer 2

Вы говорите «разные подстроки», поэтому для начала используйте набор вместо списка, чтобы дублированные подстроки не сохранялись и чтобы вы получили O (1) время поиска.Кроме того, вам не нужен модуль до конца, и Python поддерживает добавление сколь угодно больших целых чисел, поэтому вам не обязательно нужен модуль внутри вашего цикла.Наконец, я бы попробовал это, используя понимание, чтобы Python мог зацикливаться быстрее.Вот что оставляют вам эти рекомендации:

def superFunctionalStrings(s):
    a=list()
    thesum=0
    length = len(s) + 1
    modu=10**9 + 7
    substrs = {s[j:i] for j in range(length) for i in range(j+1, length)}
    return sum(len(b) ** len(set(b)) for b in substrs) % modu

Я получаю ускорение в 15-20 раз благодаря этому подходу.