Как найти подстроку в python?

ferdir, Поняла в чем проблема задачи, тут перебором очень долго считать
Если потратить время на то чтобы понять по каким закономерностям можно сократить количество нужных вариантов, то можно значительно сократить количество вычислений. Вот тут xn--o1acm.xn--80aaahbr4a1c.xn--p1acf/theory/lucky/... подробно расписано о методе динамического программирования в контексте аналогичной задачи

Мой вариант решения такой:

# Принимаем количество символов номера
len_cymb = int(input())

# Создаем таблицу с заполненными нулями, где количество столбцов - это максимальная сумма чисел +1
# а количество строк - количество пар символов в искомом номере
matrix = [[0]*(int(len_cymb*4.5)+1) for _ in range(len_cymb//2+1)]

# Задаем первую ячейку для начала суммирования
matrix[0][0] = 1
# Заполняем таблицу так, чтобы каждое значение ячейки [i][j] было суммой всех значений 
# от [i-1][j] до [i-1][j-9]
for i in range(len_cymb//2+1):
    for j in range(i*9+1):
        for k in range(10):
            if j-k>=0:
                matrix[i][j] += matrix[i-1][j-k]

# Ответом задачи является сумма квадратов всех значений последней строки таблицы
result = sum([a**2 for a in matrix[-1]])
print(result)

А ты где берешь такие задачки?