IndexError: string index out of range - в чем причина?

Алгоритмическая сложность Вашего кода составляет квадрат, все то же самое можно сделать и за линейное время. Можно сгенерировать простой тест следующим кодом и посмотреть как растет время работы с ростом длины строки:

import random
s = ''.join(random.choice('abcd') for _ in range(10**5))