So I tried to solve the problem using a suffix array, and my algorithm runs in O(nlogn). I got a TLE on the largest test case (namely "aaaa...bcaaa...aa") has a length of 1000. I tried to change different parts of code to make it better, but I had no success. After that I tried to return the original string if the length was equal to 1000. To my sheer surprise, the code was judged TLE on the same test case. After that I submitted an accepted solution to check if it would get an accepted verdict again, and the judge did accept it. So, I believe there are some issues with the judge, because it keeps TLEing my code on the largest test case even if I do absolutely nothing with that string. Hope an admin would help me with this situation. Here is my code:

```
class Solution {
char A[3100];
pair < pair<int, int>, int> L[3100];
int P[16][3100], N, stp, cnt;
int lcp(int x, int y)
{
if(y>= N)
return 0;
int k, ret = 0;
if (x == y) return N - x;
for (k = stp - 1; k >= 0 && x < N && y < N; k--)
if (P[k][x] == P[k][y])
x += 1 << k, y += 1 << k, ret += 1 << k;
return ret;
}
void constructSArray()
{
int i;
for (i = 0; i < N; i++)
P[0][i] = A[i];
for (stp = 1, cnt = 1; cnt >> 1 < N; stp++, cnt <<= 1)
{
for (i = 0; i < N; i++)
{
L[i].first.first = P[stp - 1][i];
L[i].first.second = i + cnt < N ? P[stp - 1][i + cnt] : -1;
L[i].second = i;
}
sort(L, L + N);
for (i = 0; i < N; i++)
P[stp][L[i].second] = i > 0 && L[i].first.first == L[i - 1].first.first && L[i].first.second == L[i - 1].first.second ? P[stp][L[i - 1].second] : i;
}
}
public:
string longestPalindrome(string s) {
if(s.length() == 1000)
return s;
int i;
int sLen = s.size();
if (!sLen)
return 0;
N = sLen << 1;
N++;
i = 0;
int j = N-1;
for(auto x: s)
{
A[i++] = x;
A[j--] = x;
}
A[sLen] = (char)127;
A[N] = 0;
constructSArray();
int prv = -1;
int ans = 1, lptr = 0, rptr, cur;
for(i=0; i<sLen; i++)
{
cur = lcp(i+1, N-i);
cur <<= 1;
cur++;
if(cur>ans)
{
ans = cur;
lptr = i - (cur>>1);
}
cur = lcp(i+1, N - i - 1);
cur <<= 1;
if(cur>ans)
{
ans = cur;
lptr = 1 + i - (cur>>1);
}
}
string ret = "";
for ( i = lptr ; i<ans+lptr; i++)
ret += A[i];
return ret;
}
};
```