[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

Not sure about the problems that you're facing. This answer is correct, addresses your problems.

Apart from that, this'll also get through and is similarly a dynamic programming method, just like yours:

#include <cstdint>
#include <string>

const static struct Solution {
    using SizeType = std::uint_fast16_t;
    static std::string longestPalindrome(const std::string s) {
        const SizeType slen = std::size(s);

        if (slen < 2) {
            return s;
        }

        SizeType maxlen = 0;
        SizeType head = 0;
        SizeType curr = 0;

        while (curr < slen) {
            SizeType left = curr;
            SizeType right = curr;

            while (right < slen - 1 and s[right] == s[-~right]) {
                ++right;
            }

            curr = -~right;

            while (right < slen - 1 and left > 0 and s[-~right] == s[left - 1]) {
                ++right;
                --left;
            }

            SizeType templen = -~right - left;

            if (templen > maxlen) {
                head = left;
                maxlen = templen;
            }
        }

        return s.substr(head, maxlen);
    }
};


// -~x is simply x + 1;

---

References

• For additional details, please see the Discussion Board which you can find plenty of well-explained accepted solutions in there, with a variety of languages including efficient algorithms and asymptotic time/space complexity analysis^{1, 2}.

Answer 2

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