LeetCode on Longest Palindromic Substring in Python

Question

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":

"glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt"

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?

---

enter image description here

• user228914: Would you like to see other solutions too?

Answer 1

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]

enter image description here

Your Solution

• 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]

enter image description here

• 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]

enter image description here

• 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.

---

With some comments:

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]
Solution().longestPalindrome("glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt")

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! ( ˆ_ˆ )

• user228914: better than 94%, that's nice!
• Teepeemm: 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.
• Teepeemm: @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.
• user5235: @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: 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.