Finding longest palindromic substring in a string (gives TLE on leetcode)

Question

I'm solving the Longest Palindromic Substring problem on LeetCode.

And here's my final submission:

public static String longestPalindrome(String s)
{
    // to avoid TLE
    char [] sChars = s.toCharArray();

    StringBuilder tempSb = new StringBuilder();
    StringBuilder sbForCompPalindrome = new StringBuilder();


    StringBuilder finalResult = new StringBuilder();

    for (int i = 0; i < sChars.length; i++)
    {
        tempSb.append(sChars[i]);

        if (tempSb.length() > finalResult.length() &&
                isPalindrome(sbForCompPalindrome, tempSb.toString()))
        {
            finalResult.setLength(0);
            finalResult.append(tempSb);
        }

        if (i == sChars.length - 1 &&
                finalResult.length() < sChars.length)
        {
            // reset the loop and start from next character
            tempSb.setLength(0);
            i = -1;
            sChars = Arrays.copyOfRange(sChars, 1, sChars.length);
        }
    }

    return finalResult.toString();
}

public static boolean isPalindrome(StringBuilder sb, String s)
{
    sb.append(s);
    boolean isPalindromeResult = sb.reverse().toString().equals(s);
    sb.setLength(0);
    return isPalindromeResult;
}

It seems to work as expected but it gives me TLE (Time Limit Exceeded) on the website. To add insult to injury, the input on which it gives me the error is always different (usually it's >850 char string).

I admit that my solution leaves much to be desired but it executes under 90 ms even on a 900+ char string; sadly that's the best one I could come up with even after having been a programmer for 4 years...

Could anyone give me advice on how to improve the solution? Something which is not over my head, please...

Answer 1

Avoid unnecessary operations

Thinking about unnecessary operations is important in general, especially in functions that are called very frequently. Let's take a look at isPalindrome.

To check if a string is palindrome, you can compare characters pairwise from the ends, closing in toward the middle. You can abort as soon as you find a difference. This is possible in a single pass, visiting all letters at most once.

The current code does it differently. It builds the reverse of the string, and then checks if it's equal to the original. That works, and it sounds simple, but let's take a closer look at the steps involved. Here's the current code, I added comments for each step to explain what's happening in detail:

// visits all characters of the string; full pass #1
sb.append(s);

boolean isPalindromeResult = sb
  // visits and overwrites all characters of the string; full pass #2
  .reverse()
  // allocates a new char[] to hold a new String, copies all characters; full pass #3 + allocation
  .toString()
  // visits characters until first difference; partial pass
  .equals(s);

3 full passes, 1 partial pass, and 1 array allocation. That's significantly slower than a single partial pass:

public static boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

Even though the time complexity is actually the same, this is a significant improvement. This is not enough to pass on leetcode consistently. (They seem to randomize the test data.)

---

Speaking of isPalindrome, let's also look at how it's called:

if (tempSb.length() > finalResult.length() &&
        isPalindrome(sbForCompPalindrome, tempSb.toString()))

Can you catch the unnecessarily expensive operation there?

Calling tempSb.toString() will create a new String instance, which involves the allocation of a new character array, and copying elements from the original.

It would be better to use tempSb directly, no need to create a new string from it. (If you change the signature of the simplified isPalindrome above to take a StringBuilder instead of String, it just works.)

---

Another unnecessarily expensive operation that stands out is this:

sChars = Arrays.copyOfRange(sChars, 1, sChars.length);

Array copying is expensive in general, because it requires allocation of memory, and visiting the elements copied. Instead of doing this, you could track the starting position, and restart from there, no need to copy the array:

for (int i = 0, start = 0; i < sChars.length; i++)
{
    // ... (rest of the loop unchanged) ...

    if (i == sChars.length - 1 &&
            finalResult.length() < sChars.length)
    {
        // reset the loop and start from next character
        tempSb.setLength(0);
        start++;
        i = start - 1;
    }
}

Staying sane

The intended use case of a counting for-loop is that you can see in the for statement itself how the counter advances. Manipulating the loop counter is not recommended in the loop body, and I think it's a step on the path to insanity, where you lose clarity of how the code works, the implementation spinning out of your control.

Whenever you feel the need to manipulate the loop counter in the loop body, I think it's good to take a step back and think. Why do you want to modify the loop counter? You want to reset it to the next starting position, but only after the last character. Process all characters from the start, then process all characters again but from start + 1, then process all characters again but from start +2, and so on... Well that really sounds like wrapping the loop within another loop!

for (int start = 0; finalResult.length() < sChars.length - start; start++)
{
    for (int i = start; i < sChars.length; i++)
    {
        tempSb.append(sChars[i]);

        if (tempSb.length() > finalResult.length() &&
                isPalindrome(tempSb.toString()))
        {
            finalResult.setLength(0);
            finalResult.append(tempSb);
        }
    }
    
    tempSb.setLength(0);
}

Do you really need substrings?

At this point, I think it starts to stand out that the string builder are not really doing much useful...

• The content of finalResult is replaced when a longer candidate is found. Repeatedly replacing the content of a StringBuilder is not what the tool was designed for. So it's good to start questioning whether what we're doing actually makes sense.
• The content of tempSb is used to know the current length, and for isPalindrome. We could possibly use an int to track length. And the main logic of isPalindrome is based on character indexes. Probably it would be easy to generalize it to check for palindrome over a range of start-end indexes within a string, instead of the entire string.

In short, the current usage doesn't seem to be a good fit for the intended use case of StringBuilder. We can easily replace the string builders with integers to track important indexes and lengths:

char[] chars = s.toCharArray();

int longestStart = 0;
int longestLength = 0;

for (int left = 0; longestLength < chars.length - left; left++) {
    for (int right = left; right < chars.length; right++) {
        int length = right - left + 1;
        if (length > longestLength && isPalindrome(chars, left, right)) {
            longestStart = left;
            longestLength = length;
        }
    }
}

return s.substring(longestStart, longestStart + longestLength);

I believe so far this is still the same logic as in the original code. It's doing the equivalent logical steps, but working with indexes and lengths instead of building substrings. Notice that I used left and right the same way as they are used in isPalindrome, because I expect this should help understanding the entire program.

Written this way, the length > longestLength condition sticks out. Basically it "waits" for right to be big enough, as it is incremented one by one. We don't have to wait for that, we can incorporate this in the initialization of the loop, to start right away from the first useful index or not at all, and get rid of unnecessary iterations and a condition, by changing the middle part:

    for (int right = left + longestLength; right < chars.length; right++) {
        int length = right - left + 1;
        if (isPalindrome(chars, left, right)) {

So far, we haven't changed the order of time complexity of the implementation. But by reducing the unnecessarily expensive operations such as repeated iterations, array copies, string building, we reached a point where the solution comfortably passes on leetcode, and I think it's a lot easier to read too.

Doing even better

Leetcode makes public the solutions for some of the puzzles. As of today the solution to this problem is public, and quite interesting, especially the "expand around the center" idea (realizing that there are \$2n - 1\$ possible centers), and the time complexity analysis of various approaches.