I want to print the longest palindrome in a string , I have written the code but this is giving wrong answer for some test cases . I am not able to find the error in my code . Anyone help me with this , Anyhelp would be appreciated.

Input

vnrtysfrzrmzlygfv

Output

v

Expected output

rzr

Code:

class Solution {
public:
    int ispalindrome(string s)
    {
        string rev = "";
        int n = s.size();
        for (int i = n - 1; i >= 0; i--) {
            rev = rev   s[i];
        }
        if (rev == s) {
            return 1;
        }
        return 0;
    }
    string longestPalin(string S)
    {
        // code here
        int size = S.size();
        int size_of_substr = 0;
        string ans;
        for (int i = 0; i < size; i  ) {
            for (int j = i   1; j < size; j  ) {
                string s2 = S.substr(i, j);
                if (ispalindrome(s2)) {
                    if (s2.size() > size_of_substr) {
                        ans = s2;
                        size_of_substr = s2.size();
                    }
                    else {
                        continue;
                    }
                }
                else {
                    continue;
                }
            }
        }
        return ans;
    }
};

CodePudding user response：

You are using substr(.) incorrectly. The second argument is the size of the substring.

string s2 = S.substr(i, j); should be replaced by string s2 = S.substr(i, j-i 1);

Moreover, this code will not be very efficient. To speed it up, I modified your code in the following way:

1. I pass the string by reference to the ispalindromefunction
2. I modified the algorithm to check if the substring is a palindrome. It returns false after the first mismatch
3. I don't build each substring explicitly. I only pass the start and beginning of the substring to the helper function
4. I start by checking if there exists a palindrome of the maximum size, and then I decrease its length. As soon as a palindrome is found, we know it has the maximum size, and we can stop the search

#include <iostream>
#include <string>

class Solution {
public:
    int ispalindrome(const std::string& S, int i, int j) {
        while (i < j) {
            if (S[i  ] != S[j--]) return 0;
        }
        return 1;
    }
    std::string longestPalindrome(const std::string& S) {
        int size = S.size();
        int imax = 1;
        for (int size_of_substr = size; size_of_substr > 0; size_of_substr--, imax  ) {
            int j = size_of_substr - 1;
            for (int i = 0; i < imax; i  , j  ) {
                if (ispalindrome(S, i, j)) {
                        std::string ans = S.substr(i, size_of_substr);
                        return ans;
                }
            }
        }
        return "";
    }
};

int main() {
    Solution sol;
    std::string S;
    std::cin >> S;
    auto ans = sol.longestPalindrome(S);
    std::cout << ans << "\n";
    return 0;
}