Please, give me some hard tests because I have TLE#8 too...
For example
  250000
  aaaaa...ab
  aaaaa...ba

and

  250000
  aaa..d..aaa
  aaa..f..aaa
my program can do