Leetcode 5: Longes Palindrome Substring

user_19366064 0
Viewed 180

I have been working on the LeetCode problem 5. Longest Palindromic Substring:

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

But I kept getting time limit exceeded on large test cases.

I used dynamic programming as follows:

dp[(i, j)] = True implies that s[i] to s[j] is a palindrome. So if s[i] == str[j] and dp[(i+1, j-1]) is set to True, that means S[i] to S[j] is also a palindrome.

How can I improve the performance of this implementation?

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = {}      
        res = ""
        
        for i in range(len(s)):
            # single character is always a palindrome
            dp[(i, i)] = True
            res = s[i]
        
        #fill in the table diagonally
        for x in range(len(s) - 1):
            i = 0
            j = x + 1
            while j <= len(s)-1:
                if s[i] == s[j] and (j - i == 1 or dp[(i+1, j-1)] == True):
                    dp[(i, j)] = True
                    if(j-i+1) > len(res):
                        res = s[i:j+1]
                else:
                    dp[(i, j)] = False
                i += 1
                j += 1

        return res
algorithm python
4 Answers

I think the judging system for this problem is kind of too tight, it took some time to make it pass, improved version:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = {}
        res = ""
        for i in range(len(s)):
            dp[(i, i)] = True
            res = s[i]

        for x in range(len(s)): # iterate till the end of the string
            for i in range(x): # iterate up to the current state (less work) and for loop looks better here
                if s[i] == s[x] and (dp.get((i + 1, x - 1), False) or x - i == 1):
                    dp[(i, x)] = True
                    if x - i + 1 > len(res):
                        res = s[i:x + 1]
        return res
user_99267210

Here is another idea to improve the performance:

The nested loop will check over many cases where the DP value is already False for smaller ranges. We can avoid looking at large spans, by looking for palindromes from inside-out and stop extending the span as soon as it no longer is a palindrome. This process should be repeated at every offset in the source string, but this could still save some processing.

The inputs for which then most time is wasted, are those where there are lots of the same letters after each other, like "aaaaaaabcaaaaaaa". These lead to many iterations: each "a" or "aa" could be the center of a palindrome, but "growing" each of them is a waste of time. We should just consider all consecutive "a" together from the start and expand from there onwards.

You can specifically deal with these cases by first grouping consecutive letters which are the same. So the above example would be turned into 4 groups: a(7)b(1)c(1)a(7)

Then let each group in turn be taken as the center of a palindrome. For each group, "fan out" to potentially include one or more neighboring groups at both sides in "tandem". Continue fanning out until either the outside groups are not about the same letter, or they have a different group size. From that result you can derive what the largest palindrome is around that center. In particular, when the case is that the letters of the outer groups are the same, but not their sizes, you still include that letter at the outside of the palindrome, but with a repetition that corresponds to the least of these two mismatching group sizes.

Here is an implementation. I used named tuples to make it more readable:

from itertools import groupby
from collections import namedtuple

Group = namedtuple("Group", "letter,size,end")

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ""
        x = 0
        groups = [Group(group[0], len(group), x := x + len(group)) for group in 
                   ("".join(group[1]) for group in groupby(s))]
        for i in range(len(groups)):
            for j in range(0, min(i+1, len(groups) - i)):
                if groups[i - j].letter != groups[i + j].letter:
                    break
                left = groups[i - j]
                right = groups[i + j]
                if left.size != right.size:
                    break
            size = right.end - (left.end - left.size) - abs(left.size - right.size)
            if size > len(longest):
                x = left.end - left.size + max(0, left.size - right.size)
                longest = s[x:x+size]

        return longest
user_54598390

Alternatively, you can try this approach, it seems to be faster than 96% Python submission.

 def longestPalindrome(self, s: str) -> str:
        N = len(s)
        
        if N == 0: 
            return 0
        
        max_len, start = 1, 0
        
        for i in range(N):
            df = i - max_len
            if df >= 1 and s[df-1: i+1] == s[df-1: i+1][::-1]:
                start = df - 1
                max_len += 2
                continue

            if df >= 0 and s[df: i+1] == s[df: i+1][::-1]:
                start= df 
                max_len += 1
        return s[start: start + max_len]
user_107607680

If you want to improve the performance, you should create a variable for len(s) at the beginning of the function and use it. That way instead of calling len(s) 3 times, you would do it just once. Also, I see no reason to create a class for this function. A simple function will outrun a class method, albeit very slightly.

user_151999880
Related