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

Barracks

Bug at if(ret!=0){ret = val + ret;return ret;} line, remove it and see ans. Small input and check manually. Add if(ret!=0) return val+ret; – Syncretize

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

Cann

I think it still fails for "baabdaad" gives answer 5 instead of 4 – Barracks

I actually believe that you can prove that if S[x] == S[y] it is enough to consider the case of x + 1, y - 1, val + 2, no need to check two other cases. The only issue with the code is the second one you pointed out. – Venomous

I dont know why but "baabdaad" still gives answer 5 instead of 4 – Barracks

@Tanvi, actually, you should remove the third variable, because, the result of dp[x][y] is not val, so wait for my update. – Cann

@Venomous it is substring, not subsequence, so I think this line should be there :) – Cann

@PhamTrung, you can't find the longest substirng like that. This is a solution for the subsequence, and the solution for the subsequence does not need to check x+1, y and x, y - 1 if the characters match. It is easy to prove. Though it obviously doesn't hurt to check it :) – Venomous

@Venomous you are right, missing a condition check :) just fix it, you can see I added an if statement to make sure that this is a proper substring from x to y – Cann

Yes, this would work. For some reason I still believe that the OP is looking for a subsequence, just phrased the question poorly. To find a substring in quadratic time there's an easier solution -- just fix the middle of the palinrome, and advance in both directions for as long as the characters match. Why even bother with the recursion :) – Venomous

@Venomous at first, I have that feeling too and almost going to ask, but then I saw him set val = 0 if two characters aren't matched, so I believe he is doing this for substring :) – Cann

@PhamTrung, ah, indeed O.o – Venomous

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

Unaesthetic

use of memoization can significantly reduce the time complexity – Calida

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

Driest

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

Appreciable

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

Paz

Please, explain your answer a bit further so it s more helpful – Indianapolis

I am trying every possibility of string of size 1 to size n. passing this string into an empty string and check if the string is palindrome or not. If the string is palindrome, then I am adding it into string array. At the end, check for the palindrome string from string array with maximum length and print the length of string. – Paz

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

Larue

Welcome to SO, it is always great giving the code, however consider giving some insight on the benefits and the theory behind your implementation. This is because the question has already a higher quality and better explained response. – Chinn