Longest palindromic substring top down dynamic programming

Question

Here is the algorithm for finding longest palindromic substring given a string s using bottom-up dynamic programming. So the algorithm explores all possible length j substring and checks whether it is a valid palindrome for j in 1 to n. The resulting time and space complexity is O(n^2).

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s
    P = [[False for _ in range(n)] for _ in range(n)]
    longest = s[0]

    # j is the length of palindrome
    for j in range(1, n+1):
        for i in range(n-j+1):
            # if length is less than 3, checking s[i] == s[i+j-1] is sufficient
            P[i][i+j-1] = s[i] == s[i+j-1] and (j < 3 or P[i+1][i+j-2])
            if P[i][i+j-1] and j > len(longest):
                longest = s[i:i+j]
    return longest 

I am trying to implement the same algorithm in top-down approach with memoization.

Question: Is it possible to convert this algorithm to top-down approach?

There are many questions about longest palindromic substring, but they are mostly using this bottom-up approach. The answer in https://stackoverflow.com/a/29959104/6217326 seems to be the closest to what I have in mind. But the answer seems to be using different algorithm from this one (and much slower).

Answer 1

This problem can be solved by adding memorization to the brute force approach,

1. We need to generate each substring this will take O(n^2) time, and
2. we need to check whether the generated substring is a palindrome, this will take an additional O(n),
3. in total it will be an O(n^3) time complexity.
4. Now, adding and storing the states that we already encountered to speed up the process, the time complexity can be reduced by O(n). So the total time complexity will be O(n^2)

here's the solution:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        memo = {}
        
        def isPalindrome(left,right):
            state = (left, right)
            
            if state in memo: return memo[state]
            
            if left >= right: return True
            
            if s[left] != s[right]: return False
            
            memo[state] = isPalindrome(left+1, right-1)
            
            return memo[state]
        
        N = len(s)
        result = ''
        
        for i in range(N):
            for j in range(i,N):
                if (j-i+1) > len(result) and isPalindrome(i,j):
                    result = s[i:j+1]
        
        return result

Answer 2

I tried to code Junaed's java code to Python and it's running quite well on Leetcode but is getting Memory Limit Exceeded on one of the test cases. See if we can somehow modify this further to get a better result or if I missed something in it, please do correct me.

def longestPalindrome(self, s: str) -> str:
    
    @lru_cache(maxsize=None)
    def dp(i,j):
        if i==j:
            return True
        if i+1==j:
            if s[i]==s[j]:
                return True
            return False
        if s[i]==s[j]:
            return dp(i+1,j-1)
        return False
    self.maxlen=0
    @lru_cache(maxsize=None)
    def dp2(i,j):
        if dp(i,j):
            if (j-i+1 > self.maxlen):
                self.maxlen=j-i+1
                self.ans=s[i:j+1]
        else:
            dp2(i+1,j)
            dp2(i,j-1)
    
    self.ans=""
    i=0
    j=len(s)-1
    
    dp2(i,j)
    return self.ans

Answer 3

the problem with top down approach here is that it's hard to implement topological order . You cant run 2 for loops and use memoization with it, as this Topological order (2 for loops) gives substrings but it isn't the right T.O for palindrome as palindrome of 3 digit requires info about it's inside palindrome always(of 1 digit in this case).to know if a _ _ a is palindrome or not you must know whether _ _ is palindrome or not. Thus the Topo order you require is : x,x,xx,xx,xx,xxx,xxx,xxxx,xxxxx substrings of increasing length. I'll post Top Down approach when I code or get one.

Answer 4

#include<iostream>
#include<string>
#include<vector>

using namespace std;

bool isPalindrome(string str, int startIdx, int stopIdx, vector<vector<int>>& T) {
    const int i = startIdx;
    const int j = stopIdx - 1;

    if (i == (j + 1)) {
        return true;
    }
    if (i >= j) {
        return false;
    }
    if (T[i][j] == -1) {
        if (str[i] == str[j]) {
            T[i][j] = isPalindrome(str, startIdx + 1, stopIdx - 1, T);
        }
        else {
            T[i][j] = 0;
        }
    }
    return (T[i][j] == 1);
}

string getLongestStr(string str, int startIdx, int stopIdx, vector<vector<int>>& T) {
    if (isPalindrome(str, startIdx, stopIdx, T)) {
        return str.substr(startIdx, (stopIdx - startIdx));
    }
    else {
        string str1 = getLongestStr(str, startIdx + 1, stopIdx, T);
        string str2 = getLongestStr(str, startIdx, stopIdx - 1, T);
        return str1.size() > str2.size() ? str1 : str2;
    }
    return "";
}

string getLongestStr(string str) {
    const int N = str.size();
    vector<vector<int>> T(N, vector<int>(N, -1));
    return getLongestStr(str, 0, N, T);
}

int main() {
    string str = "forgeeksskeegfor";
    //string str = "Geeks";
    
    cout << getLongestStr(str) << endl;
    return 0;
}

Answer 5

Here is my solution recursively: Start with i = 0, j = max length if(i,j) is palindrome: then max substring length is j-1. else do recursion with (i+1,j) and (i, j-1) and take the Max between these two. Code will explain more. The code is in Java, but I hope it will give the idea how to implement it. @zcadqe wanted the idea regarding how to implement in Top-down approach. I gave the idea and as a bonus also giving the code of java for better understanding. Anyone who knows python can easily convert the code!

public class LongestPalindromeSubstringWithSubStr {
static String str;
static int maxLen;
static int startLen;
static int endLen;
static int dp[][];// 0: not calculaed. 1: from index i to j is palindrome

static boolean isPal(int i, int j) {
    if (dp[i][j] != 0) {
        System.out.println("Res found for i:" + i + " j: " + j);
        return (dp[i][j] == 1);
    }
    if (i == j) {
        dp[i][j] = 1;
        return true;
    }
    if (i + 1 == j) {// len 2
        if (str.charAt(i) == str.charAt(j)) {
            dp[i][j] = 1;
            return true;
        }
        dp[i][j] = -1;
        return false;
    }
    if (str.charAt(i) == str.charAt(j)) {
        boolean res = isPal(i + 1, j - 1);
        dp[i][j] = (res) ? 1 : 0;
        return res;
    }
    dp[i][j] = 0;
    return false;
}

// update if whole string from i to j is palindrome
static void longestPalCalc(int i, int j) {
    if (isPal(i, j)) {
        if (j - i + 1 > maxLen) {// update res
            maxLen = j - i + 1;
            startLen = i;
            endLen = j;
        }
    } else {
        longestPalCalc(i + 1, j);
        longestPalCalc(i, j - 1);
    }
}

public static void main(String[] args) {
    str = "abadbbda";
    dp = new int[str.length()][str.length()];
    longestPalCalc(0, str.length() - 1);
    System.out.println("Longest: " + maxLen);
    System.out.println(str.subSequence(startLen, endLen + 1));
}

}