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 = &quot;babad&quot; Output: &quot;bab&quot; Note: &quot;aba&quot; is also a valid answer.

Below is my code that fails the following input because of &quot;Time Limit Exceeded&quot;:

&quot;glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt&quot;

class Solution(object):

    def longestPalindrome(self, s):
        &quot;&quot;&quot;
        :type s: str
        :rtype: str
        &quot;&quot;&quot;
        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 &gt; 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?
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) &lt; 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 &gt; 0 and isPalindrome(index - right - 1, index + 1):
                left, right = index - right - 1, right + 2
            if index - right &gt;= 0 and isPalindrome(index - right, index + 1):
                left, right = index - right, right + 1
        return s[left: left + right]



Your Solution

I just tested your solution (marginally passes):

class Solution(object):

    def longestPalindrome(self, s):
        &quot;&quot;&quot;
        :type s: str
        :rtype: str
        &quot;&quot;&quot;
        if len(s) &lt; 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 &gt; 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):
        &quot;&quot;&quot;
        :type s: str
        :rtype: str
        &quot;&quot;&quot;
        if len(s) &lt; 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 &gt; 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.



With some comments:
class Solution:
    def longestPalindrome(self, s):
        if len(s) &lt; 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 &gt; 0 and isPalindrome(index - right - 1, index + 1):
                print(f&quot;Step {index - 1}: Left pointer is at {index - right - 1} and Right pointer is at {index + 1}&quot;)
                print(f&quot;Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}&quot;)
                print(f&quot;Window length: {right}&quot;)
                print(f&quot;Before: Left is {left} and Right is {left + right}&quot;)
                left, right = index - right - 1, right + 2
                print(f&quot;After: Left is {left} and Right is {left + right}&quot;)
                print(f&quot;String: {s[left: left + right]}&quot;)
                print('#' * 50)
            if index - right &gt;= 0 and isPalindrome(index - right, index + 1):
                print(f&quot;Step {index - 1}: Left pointer is at {index - right} and Right pointer is at {index + 1}&quot;)
                print(f&quot;Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}&quot;)
                print(f&quot;Window length: {right + 1}&quot;)
                print(f&quot;Before: Left is {left} and Right is {left + right}&quot;)
                left, right = index - right, right + 1
                print(f&quot;After: Left is {left} and Right is {left + right}&quot;)
                print(f&quot;String: {s[left: left + right]}&quot;)
                print('#' * 50)
        return s[left: left + right]


Solution().longestPalindrome(&quot;glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt&quot;)


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