Longest Palindromic Substring

Question

I wrote the following code for this problem. The problem is to find the longest palindromic substring. I think it is correct and is working correctly for all the test cases I entered myself. Now, the code is producing a Time Limit Exceeded Error. I know that there exists Manacher's Algorithm which does it in linear time but I thought of the following solution myself and wanted to implement it. I believe that it's time complexity is less as compared to \$\mathcal{O}(n^3)\$ and other \$\mathcal{O}(n^3)\$ solutions have been accepted which makes me feel that I am missing something important.

string = input()
longest = 0
position = 0
string = string.replace('', '^')
length = len(string)
##print(string)
for index, letter in enumerate(string):
## print()
## print('Index:', index, 'Letter:', letter)
 stretch = 1
 while string[index-stretch:index+stretch+1] == string[index-stretch:index+stretch+1][::-1]\
 and index - stretch >= 0 and index + stretch < length:
## print('Matching Strings:', string[index-stretch:index+stretch+1], string[index-stretch:index+stretch+1][::-1], 'Stretch:', stretch)
 stretch += 1
## print('Not Matched:', string[index-stretch:index+stretch+1], string[index-stretch:index+stretch+1][::-1], 'Stretch:', stretch)
 stretch -= 1
 if stretch > longest:
## print('Highest Till Now')
 longest = stretch
 position = index - stretch
##print(position, longest)
print(string[position:position+(2*longest+1)].replace('^', ''))

stretch is the extension of the palindrome on either side of its center. longest stores the length of the longest substring found till then. position stores the index of the starting letter of longest. Please ask if you have any doubts.

What I want to know is that am I missing something which is causing the program to lose its efficiency? How can I overcome it? Can you suggest some improvements to the algorithm.

Thanks.

Answer 1

First things first, I'll highlight areas I felt you should change.

1. Make a function.
2. Don't litter the program with blackbox debugging 'comments'.
3. Don't use enumerate if you don't need both index and letter.
4. It's easier to read one slice rather than two.
5. You could change your while loop to a for loop, this reduces the amount of statements in the if.

Most of these are pretty simple, and are mostly due to your debugging. I'll elaborate on 5 as it's the only one that I should need to explain.

If we rearrange both \$\text{index} - \text{stretch} >= 0\$ and \$\text{index} + \text{stretch} < \text{length}\$ to get stretch. This gets \$\text{index} >= \text{stretch}\$ and \$\text{length} - \text{index} > \text{stretch}\$. As we know the input are integers we can get both to use the same sign, >. With \$\text{index} + 1 > \text{stretch}\$. If we merge them both together we get: \$\text{min}(\text{index} + 1, \text{length} - \text{index}) > \text{stretch}\$.

This basically means you can use the following range:

for stretch in range(1, min(index + 1, length - index)):

You should note, it won't go above the largest possible stretch and so you should only do stretch -= 1 if you break from the loop.

All of this together should get you:

def get_longest_palendrome(string):
 string = string.replace('', '^')
 longest = 0
 position = 0
 length = len(string)
 for index in range(length):
 stretch = 0
 for stretch in range(1, min(index + 1, length - index)):
 text = string[index - stretch:index + stretch + 1]
 if text != text[::-1]:
 stretch -= 1
 break
 if stretch > longest:
 longest = stretch
 position = index
 position -= longest
 return string[position:position + (2*longest + 1)].replace('^', '')

---

The second I looked at string = string.replace('', '^') I thought this can't be an \$O(n^3)\$ algorithm. I don't know the actual complexity, but you instantly change the length of string to \2ドルn + 1\$. This means your function is more \$O((2n)^3)\$ or \$O(8n^3)\$

I know you normally ignore the coefficient but I think it's quite important to highlight the pitfall on doubling the size of the input.