Array

Longest palindromic substring

Pinterest LinkedIn Tumblr
A palindrome is a word or number which reads same using backward and forward.
Write a program to find a maximum-length contiguous substring of a given string that is also a palindrome.

Algorithm Explanation

Initialize the string and pass the string as an argument to the utility function.
Add the Boundaries and find the longest palindrome substring.
Remove the Boundaries.
Return the string and display the palindrome string.

Source Code

package com.dsacode.DataStructre.array;
 
import java.util.Arrays;
 
public class LongestPalindrome {
 
    public  String findLongestPalindrome(String s) {
        if (s==null || s.length()==0)
            return "";
        char[] s2 = addBoundaries(s.toCharArray());
        int[] p = new int[s2.length];
        int c = 0, r = 0;
        int m = 0, n = 0;
        for (int i = 1; i < s2.length; i++) {
            if (i>r) {
                p[i] = 0;
                m = i-1;
                n = i+1;
            } else {
                int i2 = c*2-i;
                if (p[i2] < (r-i)) {
                    p[i] = p[i2];
                    m = -1; 
                } else {
                    p[i] = r-i;
                    n = r+1; m = i*2-n;
                }
            }
            while (m >=0 && n < s2.length && s2[m]==s2[n]) {
                p[i]++; m--; n++;
            }
            if ((i+p[i])>r) {
                c = i; r = i+p[i];
            }
        }
        int len = 0; c = 0;
        for (int i = 1; i < s2.length; i++) {
            if (len < p[i]) {
                len = p[i]; c = i;
            }
        }
        char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
        return String.valueOf(removeBoundaries(ss));
    }
  
    private static char[] addBoundaries(char[] cs) {
        if (cs==null || cs.length==0)
            return "||".toCharArray();
  
        char[] cs2 = new char[cs.length*2+1];
        for (int i = 0; i < (cs2.length-1); i = i+2) {
            cs2[i] = '|';
            cs2[i+1] = cs[i/2];
        }
        cs2[cs2.length-1] = '|';
        return cs2;
    }
  
    private static char[] removeBoundaries(char[] cs) {
        if (cs==null || cs.length < 3)
            return "".toCharArray();
  
        char[] cs2 = new char[(cs.length-1)/2];
        for (int i = 0; i < cs2.length; i++) {
            cs2[i] = cs[i*2+1];
        }
        return cs2;
    } 
    public static void main(String[] args) {
        String str="aibohphobia eye radar otto";
        System.out.println("Palindrome word to find the longest  palindrome: " + str);
        LongestPalindrome obj = new LongestPalindrome();
        System.out.println("Longest palindrome from given string: "+obj.findLongestPalindrome(str));
    }
 
}

Output

Palindrome word to find the longest palindrome: aibohphobia eye radar otto
Longest palindrome from given string: aibohphobia

Write A Comment