# Confused: trivial refactoring brings a TLE n^2 code to 22ms accepted code, beating 69%?

• I used to have the following code, which checks each position with a left pointer and a right pointer. It is O(n^2) time complexity, and I got a TLE.

Later I trivially refactored the duplicate code out into a function, shown below, and I got accepted with 22ms running time which beats 69% of Java solutions.

Why such a big difference with a trivial refactoring? I resubmitted two versions for a few times and the result is consistent.

``````public String longestPalindrome(String s) {
// scan left and right, for each position i, examine the max
// odd-length palindrome centered at i, and the the even-length
// palindrome centered at i and i + 1
String maxPalindrome = "";
for (int i = 0; i < s.length(); i++) {
// odd-length palindrome centered at i
int left = i;
int right = i;
while (left >= 1 && right < s.length() - 1 && s.charAt(left - 1) == s.charAt(right + 1)) {
left--;
right++;
}
if (right - left + 1 > maxPalindrome.length()) {
maxPalindrome = s.substring(left, right + 1);
}
// even-length palindrome centered at i and i + 1
if (i < s.length() - 1 && s.charAt(i) == s.charAt(i+1)) {
left = i;
right = i + 1;
while (left >= 1 && right < s.length() - 1 && s.charAt(left - 1) == s.charAt(right + 1)) {
left--;
right++;
}
if (right - left + 1 > maxPalindrome.length()) {
maxPalindrome = s.substring(left, right + 1);
}
}
}
return maxPalindrome;
}
``````

This is the new function I have:

``````private String palindrome(String s, int currMax, int left, int right) {
while (left >= 1 && right < s.length() - 1 && s.charAt(left - 1) == s.charAt(right + 1)) {
left--;
right++;
}
if (right - left + 1 > currMax) {
return s.substring(left, right + 1);
}
return null;
}``````

• Are you sure the original code you supplied is accurate? I had a spookily similar answer to the refactored version of yours except that I accidentally had the character comparison portion of the while expression inside the loop in an if statement, which of course resulted in an infinite loop and caused a TLE. Although you're probably smarter than me and didn't make that mistake.

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