python - How do I speed up this code? longest palindrome substring problem

Question

I am working on the Leetcode problem to find the longest palindrome substring of a string. Here is my code.

def longest_palindrome_substring(string):
    
    array = [i for i in string]
    
    # keep track of which substrings are palindromes
    s = [[None for _ in range(len(array))] for _ in range(len(array))]

    # longest substring so far
    best = ""
    
    # look at successively larger substrings
    for substring_length in range(len(array)): # is actually substring length - 1 = stop - start

        # look at the substring from start to stop, inclusive
        for start, stop in zip(range(len(array) - substring_length), [x + substring_length for x in range(len(array) - substring_length)]):
            
            # is it a palindrome?
            if start == stop:
                is_p = True
            elif array[start] == array[stop]:
                if start + 1 == stop:
                    is_p = True
                else:
                    is_p = s[start + 1][stop - 1]
            else:
                is_p = False
            
            # store result
            s[start][stop] = is_p
            
            # is it the best so far?
            if is_p:
                if substring_length + 1 > len(best):
                    best = array[start:stop + 1]

    return "".join(best)

I am getting the right answers for everything, but it says this code is too slow. What can I do to speed it up?

I was trying to follow the strategy outlined here.

question from:https://stackoverflow.com/questions/65907155/how-do-i-speed-up-this-code-longest-palindrome-substring-problem

Answer 1

Doing a little analysis on your code the overview is this:

================== PerfTool ==================
task                     |aver(s) |sum(s)  |count   |std     
main loop                |   0.863|   0.863|       1|   0.000
  +-int loop             |   0.001|   0.862|     758|   0.001
    +-is_it_pal?         |   0.000|   0.092|  287661|   0.000
    +-store_res          |   0.000|   0.082|  287661|   0.000
init                     |   0.019|   0.019|       1|   0.000

overall                  |    0.18|    0.88|  576082|-       

As you can see for a string long 750 char it takes a total of 0.9s Internally. My expectation is that the most part was take by pieces:

 # is it a palindrome?
 # store result
 # is it the best so far?

But this is not true, because they took less than 0.2s of 0.8s take by internal loop.

So, the major lost of time is here:

zip(range(len(array) - substring_length), [x + substring_length for x in range(len(array) - substring_length)]):

the data preparation for the internal loop, takes 0.6s (75% of the internal loop) this is the less efficient part of whole algo. The time is spent in create and destroy tons of substrings, so the direction is to use another data structure in order to avoid this effect.