3
\$\begingroup\$

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

class Solution:
    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?

  • Can we accomplish it in \$O(n)\$ Space Complexity?


\$\endgroup\$
0

1 Answer 1

-1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.