Why my longest palindromic subsequence code is failing?

Somyadeep Shrivastava 0
Viewed 28

Question - https://leetcode.com/problems/longest-palindromic-substring/
failing for input - "aaaaa" I am maintaining a dp array where i have set to 1 for string of size one and for string of size 2 whose left and right character are same, Rest I am setting it to one in case of s[i]==s[j] && dp[i+1][j-1] ==1. Still I am not sure why the longest value returned is of length 3

class Solution {
    public:
        string longestPalindrome(string s) {
            int n = s.size();
            int dp[n][n];
            int fini=0,finj=0;
            for(int i=0; i<s.size(); i++)
                for(int j=0; j<s.size(); j++){
                    if(i==j)
                            dp[i][j]=1;
                    else
                        dp[i][j]=0;
                }
            for(int i=0; i<s.size()-1; i++){
                    if(s[i]==s[i+1]){
                        dp[i][i+1]=1;
                        fini = i;
                        finj = i+1;
                        
                    }
            }
            //cout<<dp[1][6];
            cout<<fini<<finj<<endl;
            for(int i=0; i<s.size()-1; i++){
                for(int j=i+1; j<s.size(); j++){
                    cout<<"dp"<<" "<<i<<" "<<j<<' '<<dp[i][j]<<" "<<dp[i+1][j-1]<<endl;
                    if(s[i]==s[j] && dp[i+1][j-1]){
                            dp[i][j]=1;
                            if(abs(j-i+1)>abs(finj-fini+1)){
                                fini=i;
                                finj=j;
                            }
                                    cout<<fini<<" "<<finj<<endl;
    
                        }
                    
                    }     
                                
                }
            
            return s.substr(fini, finj-fini+1);
        }
    };
dynamic-programming c++
2 Answers

I suppose you misunderstood the problem statement, palindrome is the string which reads the same either from left to right or right to left, and it can be any length, you're looking only at substrings length of 2 and only checking that both symbols are the same, it is just wrong approach

here is naïve brute force solution which accidentally passes all tests:

class Solution {
public:
    string longestPalindrome(string str) {
        const auto l = str.length();
        
        size_t si = 0;
        size_t ei = 0;
        for (size_t i = 0; i < l; i++) {
            const auto c = str[i];
            
            for (size_t j = i + (ei - si) + 1; j < l; j++) // little speed up - ei-si is the length of current longest palindrome, there is no reason to check for shorter ones
                if (str[j] == c) { // we found potential palindrome, it has equal start end end symbols, now we need check all in between
                    bool flag = true;
                    size_t s = i;
                    size_t e = j;
                    
                    while (s < e) {
                        if (str[s] != str[e]) {
                            flag = false;
                            break; // some symbols are not equal - it is not a palindrome
                        }

                        s++;
                        e--;
                    }
                    if (flag) {
                        if (j - i > ei - si) { // pick longest palindrome
                            si = i;
                            ei = j;
                        }
                    }
                }
        }
        
        return str.substr(si, ei - si + 1);
    }
};

it checks every possible substring and validates whether it is palindrome or not

Iłya Bursov0

you understood the question wrong i think, palindromes are strings that are the same read backwards. heres the answer to your problem.

#include <bits/stdc++.h>
using namespace std;
string str;
int n,maxLength,start; 
int main(){
   cin>>str;
   n=str.size();
   for(int i=0;i<str.size();i++){
      for(int j=i;j<str.size();j++){
         int f=1;
         for(int k=0;k<(j-i+1)/2;k++){
            if(str[i+k]!=str[j-k])f=0;
                if (f&&(j-i+1)>maxLength){
                start=i;
               maxLength=j-i+1;
            }
        }
      }
    }
   for(int i=start;i<start+maxLength;i++)cout<<str[i];
   return 0;
}

this code examines every substring and checks if its a palindrome, if the length is larger than the current palindrome it will store in the new palindrome.

henry0
Related