# LeetCode on Longest Palindromic Substring in Python

This is a programming question from LeetCode:

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Below is my code that fails the following input because of "Time Limit Exceeded":

class Solution(object):

def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) == 0:
return None
if len(s) == 1:
return s

P = [[False]*len(s) for i in range(len(s))]

for i in range(len(s)):
P[i][i]   = True

for i in range(len(s)-1):
P[i][i+1] = (s[i]==s[i+1])

for s_len in range(3,len(s)+1):
for i in range(len(s)+1-s_len):
P[i][i+s_len-1] = P[i+1][i+s_len-2] and (s[i]==s[i+s_len-1])

ip = 0
jp = 0
max_len = 1

for i in range(len(s)):
for j in range(len(s)):
if P[i][j] and j+1-i > max_len:
max_len = j+1-i
ip = i
jp = j
continue

return s[ip:jp+1]


I was trying to follow the following approach described in the site solution. Could anyone help to see how to make my code more efficient?

• Would you like to see other solutions too?
– user228914
Nov 1, 2020 at 3:20

### Disclaimer: Not a Code Reviewer

Here are some short comments though:

• You're looping though twice.
• That'd make it brute force.
• Brute force does usually fail for some medium and hard questions on LeetCode.

### Alternative Solution

• Here we'd loop through once:
class Solution:
def longestPalindrome(self, s):
if len(s) < 1:
return s

def isPalindrome(left, right):
return s[left:right] == s[left:right][::-1]

left, right = 0, 1
for index in range(1, len(s)):
if index - right > 0 and isPalindrome(index - right - 1, index + 1):
left, right = index - right - 1, right + 2
if index - right >= 0 and isPalindrome(index - right, index + 1):
left, right = index - right, right + 1
return s[left: left + right]



• I just tested your solution (marginally passes):
class Solution(object):

def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 1:
return s

P = [[False] * len(s) for i in range(len(s))]

for i in range(len(s)):
P[i][i] = True

for i in range(len(s) - 1):
P[i][i + 1] = (s[i] == s[i + 1])

for s_len in range(3, len(s) + 1):
for i in range(len(s) + 1 - s_len):
P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])

ip = 0
jp = 0
max_len = 1

for i in range(len(s)):
for j in range(len(s)):
if P[i][j] and j + 1 - i > max_len:
max_len = j + 1 - i
ip = i
jp = j
continue

return s[ip:jp + 1]


• Since the runtimes is high, it's possible that it would fail sometimes.

• I guess LeetCode has a time limit for each problem, maybe 10 seconds would be the limit for this specific problem.

• Probably based on the geolocation/time, the runtime would be different also.

### Just a bit more optimization:

• Please see this line for j in range(i + 1, len(s))::
class Solution(object):

def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 1:
return s

P = [[False] * len(s) for _ in range(len(s))]

for i in range(len(s)):
P[i][i] = True

for i in range(len(s) - 1):
P[i][i + 1] = (s[i] == s[i + 1])

for s_len in range(3, len(s) + 1):
for i in range(len(s) + 1 - s_len):
P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])

ip = 0
jp = 0
max_len = 1

for i in range(len(s)):
for j in range(i + 1, len(s)):
if P[i][j] and j + 1 - i > max_len:
max_len = j + 1 - i
ip = i
jp = j
continue

return s[ip:jp + 1]


• It reduces about 1 second but still not good.

• I'm sure there are more ways to optimize.

• Wait a bit! There are good Python reviewers here. Would likely help you out.

class Solution:
def longestPalindrome(self, s):
if len(s) < 1:
return s

def isPalindrome(left, right):
return s[left:right] == s[left:right][::-1]

# We set the left pointer on the first index
# We set the right pointer on the second index
# That's the minimum true palindrome
left, right = 0, 1

# We visit the alphabets from the second index forward once
for index in range(1, len(s)):
# Here we move the right pointer twice and once checking for palindromeness
# We boundary check using index - right, to remain positive
if index - right > 0 and isPalindrome(index - right - 1, index + 1):
print(f"Step {index - 1}: Left pointer is at {index - right - 1} and Right pointer is at {index + 1}")
print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
print(f"Window length: {right}")
print(f"Before: Left is {left} and Right is {left + right}")
left, right = index - right - 1, right + 2
print(f"After: Left is {left} and Right is {left + right}")
print(f"String: {s[left: left + right]}")
print('#' * 50)
if index - right >= 0 and isPalindrome(index - right, index + 1):
print(f"Step {index - 1}: Left pointer is at {index - right} and Right pointer is at {index + 1}")
print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
print(f"Window length: {right + 1}")
print(f"Before: Left is {left} and Right is {left + right}")
left, right = index - right, right + 1
print(f"After: Left is {left} and Right is {left + right}")
print(f"String: {s[left: left + right]}")
print('#' * 50)
return s[left: left + right]



### Prints:

Step 18: Left pointer is at 18 and Right pointer is at 20
Palindromeness start: 17 - Palindromeness end: 20
Window length: 2
Before: Left is 0 and Right is 1
After: Left is 18 and Right is 20
String: xx
##################################################
Step 25: Left pointer is at 24 and Right pointer is at 27
Palindromeness start: 23 - Palindromeness end: 27
Window length: 3
Before: Left is 18 and Right is 20
After: Left is 24 and Right is 27
String: ibi
##################################################
Step 462: Left pointer is at 460 and Right pointer is at 464
Palindromeness start: 459 - Palindromeness end: 464
Window length: 4
Before: Left is 24 and Right is 27
After: Left is 460 and Right is 464
String: pppp
##################################################



### Happy Coding! ( ˆ_ˆ )

• better than 94%, that's nice!
– user228914
Nov 1, 2020 at 3:51
• I believe s[left:right][::-1] can also be s[right-1:left-1:-1]. I presume that would save a bit of time as well. Nov 1, 2020 at 13:13
• @Emma I agree that s[left:right].reverse() would be different (and possibly nonsensical). I'm not seeing how reversing the slice at the same time as slicing would be different than slicing and then reversing. Nov 1, 2020 at 16:48
• @Emma: +1. Many thanks for your insights. I'm still slowly reading your "Alternative Solution". That looks very smart. I have yet "decipher" the two "if" conditions. Could you say a few words about the underlying ideas?
– user5235
Nov 2, 2020 at 21:32
• It is very interesting to see that my code could pass the tests in your snapshot. I have never seen it passed submitting it several times on my own.
– user5235
Nov 2, 2020 at 21:36