# Disparity of TLE based on languages.

• I tried to follow this solution (https://discuss.leetcode.com/topic/41047/o-n-using-idea-similar-to-lps-358-msec/2) in C++.
His original JAVA solution passes in ~358 ms (as claimed). Contrary to what's written in the title, the solution runs in no less than `O(n**2)`. I have taken note of that.
Replicating this in C++ 1 takes up 1480 ms for one large test case alone (the one with `"aaaaaa....cd......aaaa"`) and obviously times out when submitted.

This is an obvious disparity over run time costs in different languages for a test case. I know that much faster solutions exist for this problem. But the fact that a slow approach is accepted in one language and not in another is unsettling. Any suggestions on how to fix this?

This issue not entirely isolated. Another `O(n**2)` solution (https://discuss.leetcode.com/topic/47699/accepted-c-solution-easy-to-understand) seems to be accepted.

1 The rogue code looks like this:

``````class Solution {
public:
string shortestPalindrome(string s) {
int mid = s.length()/2, n = s.length();
string pre;
pair<int, int> ret;

for(int i=mid-1; i>=0; i--) {
// even length
ret = expandString(s, i, i+1);
if(ret.first == -1) {
pre = s.substr(ret.second);
reverse(pre.begin(), pre.end());
return pre + s;
}

// odd length
ret = expandString(s, i, i);
if(ret.first == -1) {
pre = s.substr(ret.second);
reverse(pre.begin(), pre.end());
return pre + s;
}
}

return "";
}

pair<int, int> expandString(string &s, int left, int right) {
while(left >= 0 && right < s.length() && (s[left] == s[right])) {
left--;
right++;
}
return make_pair(left, right);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.