Find longest Palindrome in a String in Java

This question is asked from me in an interview. To find out the largest palindrome in a string, first we need to identify the logic.

Firstly, lets see

What is a Palindrome String

A palindromic String is a string that remains the same when its characters are reversed.
The examples of palindrome string are: abba, abcba, "12333321" etc.

Lets see the various solutions to solve this problem:

Solution 1

public class TestJava {

    public static void main(String[] args) {
        System.out.println(findLongestPalindrome("12321"));
        System.out.println(findLongestPalindrome("9912321456"));
        System.out.println(findLongestPalindrome("9912333321456"));
        System.out.println(findLongestPalindrome("abb"));
    }

    static public String intermediatePalindrome(String str, int left, int right) {
        if (left > right)
            return null;
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) 
        {
            left--;
            right++;
        }
        return str.substring(left + 1, right);
    }

    public static String findLongestPalindrome(String str) 
    {
        if (str == null) {
            return null;
        }
        String longestPalindrom = str.substring(0, 1);
        for (int i = 0; i < str.length() - 1; i++) {
            String palindrome = intermediatePalindrome(str, i, i);
            if (palindrome.length() > longestPalindrom.length()) {
                longestPalindrom = palindrome;
            }

            palindrome = intermediatePalindrome(str, i, i + 1);
            if (palindrome.length() > longestPalindrom.length()) {
                longestPalindrom = palindrome;
            }
        }
        return longestPalindrom;
    }
}

Solution 2 (Native Approach)

public static String longestPalindrome(String str) {
   int maxLength = 0;
   String longestPalindrome = null;
   int length = str.length();
   // check all possible sub strings
   for (int i = 0; i < length; i++) {
      for (int j = i + 1; j < length; j++) {
         int len = j - i;
         String current = str.substring(i, j + 1);
         if (isPalindrome(current)) {
           if (len > maxLength) {
              longestPalindrome = current;
              maxLength = len;
           }
         }
      }
   }
   return longestPalindrome;
}

public static boolean isPalindrome(String str) {
   for (int index = 0; index < str.length() - 1; index++) {
      if (str.charAt(index) != str.charAt(str.length() - 1 - index)) {
         return false;
      }
   }
   return true;
}

The time complexity is O(n^3) when we examine every substring and check if it is palindromic using this approach. Therefore, this approach is just a start to find out the longest palindrome in a string in java.

Solution 3 (Dynamic Approach)

public static String longestPalindrome(String input) {
   // create new array to hold results
   int[][] array = new int[input.length() + 1][input.length() + 1];
   // reverse string input
   String sb = new StringBuffer(input).reverse().toString();

   // complete the Longest common subsequence array
   for (int index1 = 0; index1 < input.length(); index1++) {
      for (int index2 = 0; index2 < sb.length(); index2++) {
         if (input.charAt(index1) == sb.charAt(index2)) {
            array[index1 + 1][index2 + 1] = array[index1][index2] + 1;
         } else {
            array[index1 + 1][index2 + 1] = Math.max(
            array[index1 + 1][index2],
            array[index1][index2 + 1]);
         }
      }
   }
   String palindrome = "";
   int x = input.length();
   int y = sb.length();

   while (x > 0 && y > 0) {
      if (array[x][y] == array[x - 1][y]) {
         x--;
      } else if (array[x][y] == array[x][y - 1]) {
         y--;
      } else {
         if (input.charAt(x - 1) == sb.charAt(y - 1)) {
            palindrome += input.charAt(x - 1);
            x--;
            y--;
         }
      }
   }
   // return the largest palindrome
   return palindrome;
}

Solution 4

public static String longestPalindrome(String input) {
   if (input.isEmpty()) {
      return null;
   }
   if (input.length() == 1) {
      return input;
   }
   String longest = input.substring(0, 1);
   for (int i = 0; i < input.length(); i++) {
      String temp = helper(input, i, i);
      if (temp.length() > longest.length()) {
         longest = temp;
      }
      temp = helper(input, i, i + 1);
      if (temp.length() > longest.length()) {
         longest = temp;
      }
   }
   return longest;
}

// Find longest palindrome
public static String helper(String str, int begin, int end) {
   while (begin >= 0 && end <= str.length() - 1
    && str.charAt(begin) == str.charAt(end)) {
      begin--;
      end++;
   }
   return str.substring(begin + 1, end);
}

Solution 5 (Manacher Algorithm)

public class TestJava {
    private int[]  p;  
    private String s;  // original string
    private char[] t;  // transformed string

    public TestJava(String s) {
        this.s = s;
        t = preprocess(s);
        p = new int[t.length];

        int center = 0, right = 0;
        for (int i = 1; i < t.length-1; i++) {
            int mirror = 2*center - i;

            if (right > i) {
             p[i] = Math.min(right - i, p[mirror]);
            }
 
            while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
             p[i]++;
            }               
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
    }

    public char[] preprocess(String s) {
        char[] t = new char[s.length()*2 + 3];
        t[0] = '$';
        t[s.length()*2 + 2] = '@';
        for (int i = 0; i < s.length(); i++) {
            t[2*i + 1] = '#';
            t[2*i + 2] = s.charAt(i);
        }
        t[s.length()*2 + 1] = '#';
        return t;
    }
 
    public String longestPalindromicSubstring() {
        int length = 0;   // length of longest palindromic substring
        int center = 0;   // center of longest palindromic substring
        for (int i = 1; i < p.length-1; i++) {
            if (p[i] > length) {
                length = p[i];
                center = i;
            }
        }
        return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
    }

    // longest palindromic substring centered at index i/2
    public String longestPalindromicSubstring(int i) {
        i = i + 2;
        int length = p[i];
        int center = i;
        return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
    }

    public static void main(String[] args) {
        String s = "9912333321456";
        TestJava manacher = new TestJava(s);
        System.out.println(manacher.longestPalindromicSubstring());
         
    }
}

Manacher's algorithm is a complicated algorithm but it has time complexity of O(n).

Please let me know if there are any other better implementations and also provide your comments, suggestions and feedback.