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

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));
}

}

Answer 2

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 3

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 to O(n).

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 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;
}