Longest Palindromic Substring - Optimization

Question

Reference link to the question https://leetcode.com/problems/longest-palindromic-substring/

With this question of the longest palindromic substring, I saw a small optimization to pass all test cases. But, I don't know if there might exist some test cases where this would fail. Kindly help me with this.

One can see that the code only checks for strings with lengths longer than the current max palindrome. But, the loops here appear to be of O(N^3) I believe, yet the early cutoffs are placed right enough to mitigate that. Is this the right type of optimization? Usually, different approaches are designed to cut the loops themselves (N^3->N^2), rather than using conditions to work with the brute-force loops.

Queries.

1. Is this an actual optimization? Does there exist cases where this would fail?
2. What could be the least significant optimization? Such as different types of early breaks.
3. If it is an actual optimization. Is this the right type of optimization, as the overall loops still remain the same? subjective question.
4. Is there a domain of study, that focuses on this kind of optimization? I understand that it's an open-ended question. The reason behind this question is that the brute force approaches are unusable, and super optimal approaches are difficult to comprehend or to come up with. But there could exist right slicing of the total set which could be a probable least significant optimization.

P.S. I think I could be completely(or partially) incorrect here, or this might not be a valid question to ask. In that case please let me know and I can remove this post at the earliest.

Here's the code.

class Solution(object):
    def longestPalindrome(self, s):
        def check(string):
            # linear
            if len(string)==1:
                return True
            else:
                for i in range(len(string)):
                    if string[i]!=string[len(string)-1-i]:
                        return False
                return True

        maxAll  = 0
        maxStr = ""
        for i in range(len(s)):
            # linear
            if maxAll<len(s)-i:
                for j in range(len(s)):
                    if maxAll<j+1-i:
                        if check(s[i:j+1]) :
                            maxAll = j+1-i
                            maxStr = s[i:j+1]

        return maxStr

Answer 1

Is this an actual optimization? Does there exist cases where this would fail?

It is an optimisation compared to where you would still check smaller strings even though you already have a longer palindrome. It will not fail to produce the expected output.

What could be the least significant optimization? Such as different types of early breaks.

You have three places that I could identify as "optimisations":

• The two first if statements in your nested loops. Of these two, the second one is the most important: when you omit the first one, the second one will still always evaluate to False. While if you omit the second one and keep the first one, there will be useless calls of check.

• The if statement in check. This treats the case of length 1 separately to avoid the loop in the else block, but this is micro-optimisation (if any). I would mark this one as the optimisation with the least impact.

Is this the right type of optimization, as the overall loops still remain the same?

Although these are optimisations, they will not be enough to score well on this challenge. In fact, when I submitted your code to the tests, the time limit was exceeded. You must have had a lucky run.

If we stick with your approach, you could still get some improvements:

• Test for palindromes starting with the largest substring (the whole string), and then reducing the size by one and testing all substrings of that size. This way you can exit as soon as you find a palindrome. No more need to keep track of a maximum.

      for size in range(len(s), 0, -1):
          for i in range(0, len(s) - size + 1):
              if check(s[i:i+size]):
                  return s[i:i+size]
  

• The palindrome check can be done faster by not explicitly looping, but rely on the faster internal implementation of reversing a string:

      def check(string):
          return string == string[::-1]
  

With these two changes some time is gained. These might be the kind of optimisations you were looking for. Still it will not score very well.

A major improvement is based on the following observation:

Your code will regularly test substrings for being palindromes that share a common center. For instance, if the input is "abcdedxba", you may have a call check("abcdedxba") but also check("bcdedxb") and check("cdedx"). Note how they all have "e" as the center character. So they do double work. They all compare the "c" and the "x" at some point to come to the conclusion they are not palindromes. This is a waste of time and calls for an optimisation:

You could do one palindrome check for all substrings that have the same center point, and identify the largest among them. This you can do by comparing characters from the center outwards (instead of inwards as you do in check) until there is a difference. To achieve this, you would iterate over all possible center (pivot) points. Such pivot point can either be at a character, or between two characters -- and determines whether you will be looking at substrings of odd or even sizes.

Is there a domain of study, that focuses on this kind of optimization? I understand that it's an open-ended question.

The definition of "kind" of optimisation really depends on whether one considers an optimisation to be easy enough to understand or not. That is a matter of personal assessment. Maybe with the above explanation, you'll consider that the optimisation I mentioned (iterating the pivot points and determining the largest palindrome that has that point as center) is not so hard to understand...