Solving the problem: Find the longest palindrome in a random character array. Can also be used to find all possible palindromes in the same sequence. http://en.wikipedia.org/wiki/Longest_palindromic_substring

ManacherAlgorithm.java

import java.util.Arrays;

/**
 * Created by le-doude on 14/06/19.
 * <p/>
 * Did you know it is possible to find the longest palindrom in a char sequence in O(N) time.
 * Here is the solution: Manacher's algorithm.
 * http://en.wikipedia.org/wiki/Longest_palindromic_substring
 */
public class ManacherAlgorithm {

    protected static final char BUFFER_CHAR = '#';

    private static final ManacherAlgorithm instance = new ManacherAlgorithm();

    public static ManacherAlgorithm getInstance() {
        return instance;
    }

    private ManacherAlgorithm() {
    }

    public String findBiggestPalindromIn(char[] seq) {
        //Preparation of the char array
        //I put # in between the letters in order to find even length palindromes.
        char[] palSq = new char[(seq.length * 2) + 1];
        for (int i = 0; i < palSq.length; i++) {
            if (i % 2 == 0) {
                palSq[i] = BUFFER_CHAR;
            } else {
                palSq[i] = seq[(i - 1) / 2];
            }
        }
        //This array will store the lengths of all palindromes in the string at the index corresponding to the center of the palindromes
        int[] palLng = new int[palSq.length];
        Arrays.fill(palLng, 1); //fill it with ones (a single letter is by definition its own palindrome)

        int before, after;
        for (int i = 0; i < palSq.length; i++) {
            before = i - palLng[i];
            after = i + palLng[i];
            if (before < 0 || after >= palLng.length) {
                continue; //avoid index out of range
            }
            if (palSq[before] == palSq[after]) {
                palLng[i]++; //palindrom is longer by one than previously known
                palSq[after] = palSq[before]; //if there is a palindrom in the left half it is also in the right half
                i--; //stay here for now, we actually go forward with the offset but keep the center where it is.
            }
        }

        System.out.println(Arrays.toString(palSq));
        System.out.println(Arrays.toString(palLng));
        
        //We now find the longest by iterating once more (could be done on the fly but I want to make this readable)
        int ml = 0, mi = 0;
        for (int i = 0; i < palLng.length; i++) {
            if (ml < palLng[i]) {
                ml = palLng[i];
                mi = i;
            }
        }
        int beginIndex = (mi - ml) + 1;
        int endIndex = mi + ml;
        String result = String.valueOf(palSq).substring(beginIndex, endIndex).replaceAll(BUFFER_CHAR + "", "");
        System.out.println(String.format("Longest palindrome is %s", result));
        return result;
    }

}