Longest Palindromic Substring | Python Code Giving TLE

Question

Problem Statement

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

---

Constraints

• 1 ≤ s.length ≤ 1000
• s consist of only digits and English letters.

---

Algorithm

Now, there are \$\frac{n(n+1)}2\$ substrings, if a string has length \$n\$.

Because there are \$n-k+1\$ substrings of length \$k\$. Thus, total number of substrings are $$\sum_{k=1}^n(n-k+1)=n+(n-1) +(n-2) + \ldots\ldots+2+1$$

Checking if these substrings are palindrome or not take another \$O(n)\$ time. Thus, absolute brute force is \$O(n^3)\$.

But, we can reuse a previously computed palindrome to compute a larger palindrome. This reduces checking to \$O(1)\$. Thus, we can avoid unnecessary re-computations.

$$\text{isP(i,j)}=\begin{cases}\color{green}{\text{True}}, & \text{if substring } S_i\ldots S_j \text{ is a palindrome} \\ \color{red}{\text{False}}, & \text{otherwise} \end{cases}$$

Thus,

Recurrence Relation : \$\text{isP(i,j) = isP(i+1, j-1) and s[i]==s[j]}\$

Base Case

• \$\text{isP(i,i ) =} \color{green}{\text{ True}}\$
• \$\text{isP(i,i+1) = (s[i]==s[i+1])}\$

We will initialize for one-length substrings, then for two-length substrings, and so on.... Since, there is lot of overlapped subproblems, we will store computed result. For purpose of storing computed result, we will use a matrix
(or half the matrix, since we don't have to compute where \$i>j\$)

For implementing, we can use the fact that diagonal has property of constants \$j-i\$.

• \$j-i = 0\$ means substring has length \$1\$.
• To compute \$dp[i][j]\$ we need \$dp[i+1][j-1]\$
  • \$i\$ : outer loop needs to go from higher to lower
  • \$j\$ : inner loop needs to go from lower to higher

---

Code

def longestPalindrome(self, s: str) -> str:   
    n  = len(s)
    
    if n<=1: 
        return s
    
    dp = [[False]*n for _ in range(n)]
    
    for i in range(n):
        dp[i][i]  = True            
            
    #Longest Palindrome Start Index, and End
    maxS = 0
    maxE = 0
    
    for i in range(n, -1, -1):
        
        for j in range(i+1, n):
                                
            dp[i][j] = (s[i]==s[j]) and (j-i==1 or dp[i+1][j-1])
            
            if dp[i][j]:
                maxS, maxE = max ( (maxS, maxE), (i,j), key=lambda x: x[1]-x[0] )
            
    return s[maxS:maxE+1]

• Time Complexity : We are listing all substring, \$O(n^2)\$. Now, to check if it is a palindrome or not, we are doing \$O(1)\$ Computations. Hence, \$O(n^2)\$

• Space Complexity : i can vary from \$1\$ to \$n\$. j can vary from \$1\$ to \$n\$. Discard those where \$i>j\$. Thus, diagonal-half of matrix, including diagonal. Hence, \$O(n^2)\$

---

Doubts

• The code works fine, but is giving Time Limit Exceed on Leetcode. Why so? Another \$O(n^2)\$ approach for Longest Palindromic Substring [Expand around \$2n-1\$ centers] is working fine. Is time complexity of this code slower than \$O(n^2)\$?

• [Implicit Question] Any pointer for improving Time Complexity?

• If input size is \$10^3\$ only, then \$O(n^2)\$ shouldn't give TLE. Isn't it?

• Is there a way to accomplish it in \$O(n)\$ Space Complexity?

---

Answer 1

The max function adaption using a lambda that is defined at each use is unneeded complexity; you could do the same with a simple if test. However looking at your distance version, if you switch the loops around to drive distance upwards, you don't even need to check whether you have a new best palindrome - anything you find is automatically a best case so far. Also then there's a pretty obvious special case that would avoid a test in the main check loop - you can split out the distance == 1 case into a preliminary loop rather than test it. Here's how I would write your distance-based solution with just those changes:

class Solution:
    def longestPalindrome(self, s: str) -> str:   
        n = len(s)
        if n <= 1: 
            return s
        
        dp = [[False]*n for _ in range(n)]
        
        maxS = 0
        maxE = 0

        # 1-length palindromes (distance==0)
        for i in range(n):
            dp[i][i] = True 
        # 2-length palindromes (distance==1)
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True 
                maxS, maxE = i, i+1
        # Distance from 2 upwards (length >= 3)
        for distance in range(2, n):
            for st in range(n-distance):
                en = distance + st 

                if dp[st+1][en-1] and s[st] == s[en]:
                    dp[st][en] = True
                    maxS, maxE = st, en

        return s[maxS:maxE+1]

At this point you might realize that you are only looking a little way back into the dp matrix (diagonally, although could reorganize on distance instead...), and hunting for potentially sparse True values, which suggests some more algorithmic efficiencies...