[leetcode 5 ]Can't really find what's wrong in my solution for longest Palindrome substring problem

Question

input:

babad
abbd

output:

ad
bb

expected:

bab
bb

Code:

#include<iostream>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int maxlength=1;
        bool ispalindromic[1000][1000]={false};
        for(int i=0;i<s.length();i++)
            ispalindromic[i][i]=1;
                
        for(int l=2;l<s.length();l++){
            for(int i=0;i<s.length()-1; i++){
                int j=i+l-1;
                if(l==2&&s[i]==s[j]){
                    ispalindromic[i][j]=1;
                    maxlength=max(maxlength,j-i+1);
                    continue;}
                if(ispalindromic[i+1][j-1]&&s[i]==s[j]){
                    ispalindromic[i][j]=1;
                    maxlength=max(maxlength,j-i+1);
                }
            }}
        for(int i=0;i<s.length();i++){
        int j=i+maxlength-1;
            if(ispalindromic[i][j]){
                return s.substr(i,j);
            }
        }
        return s.substr(0,1);
    }
};

I created ispalindromic[1000][1000] first and made sure that every alphabet itself is palindromic. Then I check palindromic from the length of 2 and so on. Whenever ispalindromic becomes true, the code updates maxlength so that in the end the code can simply use maxlength to print longest palindromic.

Answer 1

There are some problems with this code.

1. Indices of your for loops When you consider the length l of a possible substring, your l should go between 2 to s.length(), so the outer for loop should be:

   for(int l=2;l<=s.length();l++){ You see I changed l < s.length() to l <= s.length()

2. Then your i index of inner loop should go from 0 to s.length()-l it cannot go further than that when you consider a string of length l. It needs to be modified as :

   for(int i=0;i<s.length()-l+1; i++){

3. Then if condition for l=2 should be modified as :

             if(l==2){
                if ( s[i] == s[j] ) {
                 ispalindromic[i][j]=1;
                  maxlength=max(maxlength,j-i+1);
                }
   
                continue;
            }
   

   You need to move s[i] == s[j] inside the if because irrespective of s[i] == s[j] you need to continue as per your code.

4. You need to print the substr that spans a length of maxlength so your return statement should be : return s.substr(i,maxlength);

With those corrections, the code is:

class Solution {
public:
    string longestPalindrome(string s) {
        int maxlength = 1;
        bool ispalindromic[1000][1000] = {false};

        for (int i = 0; i < s.length(); i++) {
            ispalindromic[i][i] = 1;
        }

        for (int l = 2; l <= s.length(); l++) {
            for (int i = 0; i < s.length() - l + 1; i++) {
                int j = i + l - 1;

                if (l == 2) {
                    if ( s[i] == s[j] ) {
                        ispalindromic[i][j] = 1;
                        maxlength = max(maxlength, j - i + 1);
                    }

                    continue;
                }

                if (ispalindromic[i + 1][j - 1] && s[i] == s[j]) {
                    ispalindromic[i][j] = 1;
                    maxlength = max(maxlength, j - i + 1);
                }
            }
        }

        for (int i = 0; i < s.length(); i++) {
            int j = i + maxlength - 1;

            if (ispalindromic[i][j]) {
                return s.substr(i, maxlength);
            }
        }

        return s.substr(0, 1);
    }
};