Как выловить ошибку в коде?

Question

[Sheephard]

Есть задача:

Скучная лекция
Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далёким и незаметным...
Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.
Тут ему пришла в голову мысль — времени до конца лекции всё равно ещё очень много — почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?
После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.
Макс хорошо знает любимое слово Лёши, а ещё у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Лёше пришлось выписать каждую букву.

Входные данные:
На вход подаётся строка, состоящая из строчных латинских букв, — любимое слово Лёши.
Длина строки лежит в пределах от 5 до 100000 символов.

Выходные данные:
Для каждой буквы на листочке Лёши выведите её, а затем через двоеточие и пробел — сколько раз она встретилась в выписанных Лёшей словах (см. формат вывода в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.

Примеры
Ввод
hello

Вывод
e: 8
h: 5
l: 17
o: 5

Есть код:

from math import ceil

previous = 0
d = {}
li = list(input())
mid = ceil(len(li)/2)-1

for i in range(mid+1):
    id_first = i
    id_second = len(li) - i - 1
    previous = len(li) - 2*i + previous
    f_letter = li[id_first]
    s_letter = li[id_second]

    if f_letter not in d:
        d[f_letter] = 0

    if i != mid:
        if s_letter not in d:
            d[s_letter] = 0
        d[s_letter] += previous

    d[f_letter] += previous

keys = list(d.keys())
keys.sort()

for k in keys:
    print(k + ': ', d[k])

Программа не проходит с ошибкой "Программа выдаёт неверный ответ", однако на моих тестах всё в порядке. В чём может быть проблема?

Comments

[Wataru]

Можете объяснить свое решение. Не совсем понятно, что оно делает.

Answer 1

[Wataru]

Похоже, на строке "abcdef" у вас выдаст d=0, а может и вообще d не напишет.

Проблема в том, что вы пытаетесь считать параллельно для правой и левой половины. Логично, коэффициенты там симметричные будут, но можно сделать ошибку. И ускорения ваша оптимизация практически не несет. В 2 раза меньше итераций, делающих в 2 раза больше + дополнительная проверка каждый раз. На компилируемых языках может быть еще и медленнее наивного цикла от 0 до n-1. В питоне - не знаю. Уж точно не в 2 раза быстрее, как можно было бы подумать.

Еще, я бы вместо последовательного обновления коэффициента в previous считал его явно. i-ый символ встречается ровно в (i+1)*(n-i) подстроках.

Comments

[Sheephard]

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