# Longest Palindromic Substring | Python Code Giving TLE

#### 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-x )

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?

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