Longest Palindromic substring

Question

I've been solving some questions to prepare for my midterm and I can't get my hands on what is causing the error in this one.The problem states that

"The longest palindromic substring problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. Write an Java method longestPalindrome that given a string s, it returns the longest palindromic substring. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, "aca" and "ada". Thus, your method should return the first substring with the greatest length. In this case, "aca"."

So I divided this problem into 2 methods(excluding the main method) here's my code:

public static String pali(String s){  
    int i = 0;
    int j = s.length()-1;
    String result = "";
    while (i<s.length()/2)
    {
        if (s.charAt(i) == s.charAt(j))
            if (palicheck(s.substring(i,j+1)) == true)
                break;
            i++;
            j--;
    }
    return s.substring(i,j+1);

}
public static boolean palicheck(String s){
    int i = 0;
    int j = s.length()-1;
    boolean flag = true;
    while(i<s.length()/2){
        if (s.charAt(i) == s.charAt(j) && flag == true)
            flag = true;
        else
            flag = false;
        i++;
        j--;
    }

    return flag;
}

okay, so what my code does is that it takes first and last index and checks if they're the same, IF they are it'll check if they contained string between them is a palindrome one or not if not, it'll shift them by 1 unit. My Problem is That what ever input I put in, I always get the first character of the string for example if I entered "bananas" i'll get b. Please help me! Sorry If I Left out anything It's my first time posting here.

(I'm using very basic methods of solving as It's my first year in university and my first time dealing with programming So please bear with me! ^_^).

I got it work, With only changing these:

if (palicheck(s.substring(i,j+1)) == true) break; else i++; j-- I removed the else completely, Also In Palicheck I added j-- As I have forgotten that as well

Answer 1

Given a string find the longest palindromic substring. What is palindrome? Palindrome string reads the same from backward or forward Ex: "abba", "abcba" We are looking for substring which is palindrome not subsequence (there is a difference) This questions share similarities with question finding the longest palindromic subsequence which can be solved using dynamic programming. As substring is also a subsequence we can apply the same algorithm with minor changes to find the longest palindromic substring but the solution is O(N²) and space complexity is also O(N²). There is an easier solution to solve this problem. Key observations Palindrome is symmetric around the centre.

So we can consider every point as centre and try to expand around it. Example "efeabccbafe" "e|f|e|a|b|c|c|b|a|f|e" There are total 21 centres, consider imaginary centre between characters to handle even palindrome case.

Coding this solution is easier.

public class Solution {
private int start, maxPalLen;
public String startngestPalindrome(String s) {
    int len = s.length();
    if (len < 2)
        return s;
    
    for (int i = 0; i < len-1; i++) {
        expandAroundCentre(s, i, i); // odd length
        expandAroundCentre(s, i, i+1); // even length
    }
    return s.substring(start, start + maxPalLen);
}

private void expandAroundCentre(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxPalLen < k - j - 1) {
        start = j + 1;
        maxPalLen = k - j - 1;
    }
}

}

Answer 2

C# solution:

public string LongestPalindrome(string s) {
        var n = s.Length;
            var data = new bool[n, n];
            var result = string.Empty;

            for (var len = 1; len <= n; len++)
            {
                for (var start = 0; start < n; start++)
                {
                    var end = start + len - 1;
                    if (end >= n)
                        break;
                    data[start, end] = (len == 1 || len == 2 || data[start + 1, end - 1]) && s[start] == s[end];
                    if (data[start, end] && len > result.Length)
                    {
                        result = s.Substring(start, len);
                    }
                }
            }
            return result;
    }

Answer 3

I had got this question for one interview code challenge and i solved it as above:

    import java.util.SortedMap;
import java.util.TreeMap;


public class MainClass {
    public static void main(String[] args) {
        findLargestPallindrom("aadwfaafw");
        findLargestPallindrom("billkrbatcctabrasdfasfdabcba");
        findLargestPallindrom("assdfdssa");
        findLargestPallindrom("asffsabc");
        findLargestPallindrom("bb");
    }

    private static void findLargestPallindrom(String string) {
        SortedMap<Integer, String> pallindroms = new TreeMap<>();

        int largestLength=0;
        for(int i =0; i< string.length()-1; i++)
        {
            if(string.charAt(i)==string.charAt(i+1))
            {
                largestLength =2;
                pallindroms.put(2, string.substring(i, i+2));
                //System.out.println(string.substring(i, i+2));
            }
        }

        String sub;
        //check different length of substrings for being pallindrom:
        for(int i=3; i<=string.length(); i++) {
            for(int k=0; k+i < string.length()+1; k++) {
                if(k+i+1 >= string.length()) {
                    sub = string.substring(k);
                }
                else {
                    sub = string.substring(k, k+i+1);
                }

                if(MainClass.isPallindrom(sub)) {
                    //System.out.println("added large substring is: "+sub);
                    pallindroms.put(i, sub);
                }
            }
        }

        if(!pallindroms.isEmpty()) {
            System.out.println("largest palindrome substring is:" + pallindroms.get(pallindroms.lastKey()));
        }
        else System.out.println("There is no pallindrom");
    }

    static boolean isPallindrom(String s) {
        StringBuilder sb = new StringBuilder(s);
        if(s.equals(sb.reverse().toString())) {
            return true;
        }
        return false;
    }
}

Answer 4

import java.util.Scanner;

public class palindromicSubstring {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);


        String str,substring="",longest="";

        int len,i,j,k;
        System.out.println("Enter String");
        str=sc.nextLine();
        len=str.length();
        for(i=0;i<=len;i++) {
            for(j=0,k=i;k<=len;j++) {

            substring=str.substring(j,k);
            if(palindrome(substring))
                longest=substring;
            k++;
        }
        }
        System.out.println(longest);


    }
    static boolean palindrome(String str)
    {
        int len=str.length();
        int i;
        String temp="";
        for(i=len-1;i>=0;i--) {
            temp=(temp+str.charAt(i));
        }
        if(temp.equals(str)) 
            return true;
        else return false;



    }

}