Почему ошибка времени выполнения в программе?

Question

В задаче на HackerRank, где нужно подсчитать количество подстрок Палиндрома.

Эта программа работает хорошо, пробовала с разными тестами.

Но он не проходит последние два теста на HackerRank.

Какие могут быть возможные тестовые случаи, которые моя программа не выполнила успешно.

Вот формулировка проблемы.

Имеет 1 параметр: строка, с. Он должен возвращать целое число, обозначающее количество палиндромных подстрок s.

Ограничения

1 ≤ | S | ≤ 5 × (10) ^ 3 с состоит из строчных букв английского алфавита.

Формат вывода

Ваша функция должна возвращать целое число, обозначающее количество различных палиндромных подстрок s

def countPalindromes(s):
    counter=0
    length = len(s)
    list1= ([s[i:j+1] for i in range(length) for j in range(i,length)])
    list2=([x[::-1] for x in list1])
    for i in range(len(list2)):
        if(list1[i]==list2[i]):
            counter+=1
    return counter

#input = aaa
#output = 6 i.e. {a,a,a,aa,aa,aaa}
#input = abccba
#output = 9
#input = daata
#output = 7
#output is correct though failing the last 2 test cases

Answer 1

Вы можете использовать Рекурсия и Заметка , чтобы вычислить количество подстрок палиндрома в строке. Например:

def is_palindrome(s):
    return 1 if s == s[::-1] else 0


def count_palindromes(s, i, j, m):
    key = '{}-{}'.format(i, j)
    if key in m.keys():
        return m[key]
    if i == len(s)-1 or i > j:
        return 0
    m[key] = is_palindrome(s[i:j]) + count_palindromes(s, i+1, j, m) + count_palindromes(s, i, j-1, m)
    return m[key]


m = {}
print(count_palindromes('aaa', 0, 2, m)) # should be count_palindromes(s, 0, len(s)-1, m)
# output: 6