I managed to get rid of WA using these two test cases:

in:
1
dcbbbdbdbbacaaaddbdcbbbdbbdbbadacbbaaddbaddbddacaa
out:
15577

in:
1
abcccacccbcabaaaacbbabbcaaaaacaaaaacaacacbbacbcaba
out:
15236

In test #23 it seems that n is large. So, to pass TLE #23, make sure your code is running fast enough for n = 100 000 and each test contains a single letter.