longest palindromic substring recursive solution

Question

I am aware of solutions that uses the bottom up dynamic programing approach to solve this problem in O(n^2). I am specifically looking for a top down dp approach. Is it possible to achieve longest palindromic substring using a recursive solution?

Here is what I have tried but it fails for certain cases, but I feel I am almost on the right track.

#include <iostream>
#include <string>

using namespace std;

string S;
int dp[55][55];

int solve(int x,int y,int val)
{

    if(x>y)return val;
    int &ret = dp[x][y];
    if(ret!=0){ret = val + ret;return ret;}
    //cout<<"x: "<<x<<" y: "<<y<<" val: "<<val<<endl;
    if(S[x] == S[y])
        ret = solve(x+1,y-1,val+2 - (x==y));
    else
        ret = max(solve(x+1,y,0),solve(x,y-1,0));
    return ret;
}


int main()
{
    cin >> S;
    memset(dp,0,sizeof(dp));
    int num = solve(0,S.size()-1,0);
    cout<<num<<endl;
}

Answer 1

For this case:

if(S[x] == S[y])
    ret = solve(x+1,y-1,val+2 - (x==y));

it should be:

if(S[x] == S[y])
    ret = max(solve(x + 1, y - 1, val + 2 - (x==y)), max(solve(x + 1, y, 0),solve(x, y - 1, 0)));

Because, in case you cannot create a substring from x to y, you need to cover the other two cases.

Another bug:

if(ret!=0){ret = val + ret;return ret;}

you should return ret + val and not modify ret in this case.

The main problem is you store the final val into dp[x][y], but this is not correct.

Example:

acabc , for x = 1 and y = 1, val = 3, so dp[1][1] = 3, but actually, it should be 1.

Fix:

int solve(int x,int y)
{  
    if(x>y)return 0;
    int &ret = dp[x][y];
    if(ret!=0){return ret;}

    if(S[x] == S[y]){
        ret = max(max(solve(x + 1, y),solve(x, y - 1)));
        int val = solve(x + 1, y - 1);
        if(val >= (y - 1) - (x + 1) + 1)
            ret = 2 - (x == y) + val;
    }else
        ret = max(solve(x+1,y),solve(x,y-1));
    return ret;
}

Answer 2

Longest Palindrome using Recursion in Javascript:

const longestPalindrome = str => {
  if (str.length > 1){
    let [palindrome1, palindrome2] = [str, str];
    for (let i=0;i<Math.floor(str.length/2);i++) {
      if(str[i]!==str[str.length-i-1]) {
        palindrome1 = longestPalindrome(str.slice(0, str.length-1));
        palindrome2 = longestPalindrome(str.slice(1, str.length));
        break;
      }
    }
    return palindrome2.length > palindrome1.length ? palindrome2 : palindrome1;
  } else {
    return str;
  }
}

console.log(longestPalindrome("babababababababababababa"));

Answer 3

here is the python solution for this:

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:
                memo[state] = True
                return True
            
            if s[left] != s[right]: 
                memo[state] = False
                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

Try this instead for getting longest palindromic subsequence length using c++

#include<bits/stdc++.h>
using namespace  std;
int dp[100][100];
int solve(string s,int start, int end){
    if(start==end){
        return 1;
    } 
    if(start>end) return 0;
    if(dp[start][end]!=-1) return dp[start][end];
    if(s[start]==s[end]) {
        int temp_st=start,temp_end=end;
        while(s[temp_st]==s[temp_end]){
            temp_st++;
            temp_end--;
            if(temp_st>temp_end) break;
        }
        if (temp_st>temp_end){
            return dp[start][end]=2+solve(s,start+1,end-1);
        }
        else return dp[start][end]=max(solve(s,start+1,end-1),max(solve(s,start+1,end),solve(s,start,end-1)));
        }
    else{
        return dp[start][end]=max(solve(s,start+1,end),solve(s,start,end-1));
    }
}
int main(){
    string s;
    cin>>s;
    memset(dp,-1,sizeof(dp));
    int count=solve(s,0,s.length()-1);
    cout<<count<<endl;
    return 0;
}

Answer 5

/*C++ program to print the largest palindromic string present int the given string
eg. "babad" contains "bab" and "aba" as two largest substring.
by occurance, "bab" comes first hence print "bab".
*/

#include<bits/stdc++.h>
using namespace std;
bool ispalindrome(string s)
{
    int l = s.length()-1;
    int r = 0;
    while(l>r){
        if(s[l]!=s[r])
            return false;
        l--;r++;
    }
    return true;
}
int main()
{
    string str,str1,str3;
    vector<string> str2;
    cin>>str;
    int len = str.length();
    for(int i=0;i<len;i++)
    {
        for(int j=i;j<=len;j++)
        {
            str1 = "";
            str1.append(str,i,j);
            if(ispalindrome(str1)){
                str2.push_back(str1);
            }
        }
    }
    int max = 0;
    for(int i=0;i<str2.size();i++)
    {
        if(str2[i].length()>max){
            max = str2[i].length();
            str3 = str2[i];
        }
    }
    cout<<"MAXIMUM LENGTH IS : "<<max<<"\nLARGEST PALINDROMIC STRING IS : "<<str3<<endl;
    return 0;
}

Answer 6

#include <iostream>
using namespace std;
int ans=0;
bool fn(string &s,int i,int j){
    if(i==j)
    return 1;
    if((j-i)==1&&s[i]==s[j])
    return 1;
    else if((j-i)==1&&s[i]!=s[j])
    return 0;
    if(s[i]==s[j]){
        if(fn(s,i+1,j-1)){
            ans=max(ans,j-i+1);
            return 1;
        }
        else{
            return 0;
        }
    }
    else{
        fn(s,i,j-1);
        fn(s,i+1,j);
        return 0;
    }
}
int main() {
    string s;
    cin>>s;
    int last=s.length()-1;
    fn(s,0,last);
    cout<<ans<<endl;
    return 0;
}