AtCoder Beginner Contest 215 E

https://atcoder.jp/contests/abc215/tasks/abc215_e

ただのDPで、PyPy2だとあっさり通りました。
で、Python3で試したら、24ケース中13ケースでTLE。案の定Pythonでは遅いです。
手元でも試したら、実行時間は元の文字列の長さにだいたい比例するので、長さ少し変えて、

length Python2 PyPy2
1000 1.92s 0.25s
2000 3.83s 0.44s
4000 7.80s 0.84s

だいたいPyPy2のほうが9倍くらい速いですね。長いリストを使うとだいたいこんな感じです。
たいていの場合PyPyのほうが速いので、素直にPyPyを使いましょう。