Longest palindromic substring missing an edge case

Question

This is code I have written using dynamic programming concepts.

bool ispalin(string s)
    {
        string s1=s;
        reverse(s.begin(),s.end());
        if(s1.compare(s)==0)
            return true;
        return false;
    }
    string longestPalindrome(string s) {
       int n = s.length();
        if(n==1)
            return s;
       
        vector<vector<int>> dp(n,vector<int>(n,0));
        pair<int,int>coor;
        for(int i =0;i<n;i++)
        {
            dp[i][i]=1;
            coor=make_pair(i,i);
        }
        for(int i=0;i<n;i++)
        {
            int j=i+1;
            if(j<n)
            {
                if(ispalin(s.substr(i,j)))
                   {
                       dp[i][j]=1;
                       coor=make_pair(i,j);
                   }
                   else
                   {
                       dp[i][j]=0;
                   }
            }
        }
        for(int i=0;i<n;i++)
       {
            for(int j=2;j<n;j++)
            {
                if(i<j)
                {
                    if(s[i]==s[j] && dp[i+1][j-1]==1)
                    {
                        dp[i][j]=1;
                        coor=make_pair(i,j);
                    }
                    else
                        dp[i][j]=0;
                }
            }
       }
        return s.substr(coor.first,coor.second);
                   
    }

What I have tried to do is

1. first for loop is to fill the diagonal elements.
2. for loop is to fill elements for length 2 i.e - I check if that substring is palindrome if yes I make it 1 else 0.
3. Whenever I update a cell to 1 I store coor pair to those coordinates so that they always have the latest values where 1 was updated.

It does not work on cases "bb", "ccc" how am I missing this case in the code?

Answer 1

The way you are using substr function is not correct. First argument should be the starting index and the second argument is the length of string.

Your code must be failing for this string as well "abccbdf".

Change

if(ispalin(s.substr(i,j)))

to this

if(ispalin(s.substr(i,2)))

And, in last return statement, your "coor" have correct value, but "substr" second argument is incorrect. Use this statement instead:

return s.substr(coor.first,coor.second-coor.first+1);