Finding longest palindromic string

Solution.java

import java.util.Objects;

/**
 * https://leetcode.com/problems/longest-palindromic-substring/description/
 * Run time: 10 ms
 * Time complexity: O(N)
 * Space complexity: O(N)
 * Keyword: palindrome, Manacher’s Algorithm
 * 
 * Ref: https://articles.leetcode.com/longest-palindromic-substring-part-ii/
 */
class Solution {

    public String longestPalindrome(String s) {

        // Imagine that for string "abac", we build another string by inserting
        // place holders in-between. "#a#b#a#c"
        // The value is the at index i is the half length of the max palindrome centered at i of
        // the modified string.
        // The half length include the number of characters to the left or right of the
        // center character. E.g. For "#a#b#a#c", the half length for the center at index
        // 3 will be 3 because the max palindrome is "#a#b#a#".
        // You can observe that it will actually also be the full length of the palindrome
        // for the original string no matter the original palindrome has odd or even length.
        int[] palindromeLen = new int[s.length() * 2];

        // The max length of the palindrome we have seem so far
        int maxPalindromeLen = 0;

        // The center of the max palindrome of the modified string
        int maxPalindromeCenter = 0;

        // The index of the palindrome center that has the largest right boundary
        // The palindrome will be used for speeding up.
        int refCenter = 0;

        // The right boundary of the palindrome.
        // E.g. for "#a#b#a#d#", the right boundary of center 3 will be 6
        int refRightBoundary = 0;
        for (int idx = 1; idx < palindromeLen.length; idx++) {

            // The mirroring index for the center index
            int mirrorIdx = refCenter - (idx - refCenter);

            // If the current index is within the range of the referencing palindrome,
            // then we know the least palindrome length.
            palindromeLen[idx] = (idx < refRightBoundary) ?
                    Math.min(refRightBoundary - idx, palindromeLen[mirrorIdx]) : 0;

            // Check if we can extend the palindrome further
            while (true) {

                int rightIdx = idx + palindromeLen[idx] + 1;
                int leftIdx = idx - palindromeLen[idx] - 1;

                // If the left or right index is even (they will be even/odd at the same time),
                // then the left and right indices are pointing to the inserted delimiter "#", and
                // the characters should be the same.
                // Otherwise, we go back to the original string to check whether the characters are the same.
                if ((leftIdx % 2) == 0 ||
                        (rightIdx < palindromeLen.length && leftIdx >= 0 &&
                        s.charAt(leftIdx / 2) == s.charAt(rightIdx / 2))) {
                    palindromeLen[idx]++;
                } else {
                    break;
                }
            }

            // If we find that the right boundary of the current palindrome is larger, then we
            // update the referencing palindrome.
            if (idx + palindromeLen[idx] > refRightBoundary) {
                refCenter = idx;
                refRightBoundary = idx + palindromeLen[idx];
            }

            // Update the max palindrome we have seen so far
            if (palindromeLen[idx] > maxPalindromeLen) {
                maxPalindromeLen = palindromeLen[idx];
                maxPalindromeCenter = idx;
            }
        }

        // For string "#a#a#b#", the max palindrome is "#a#a#", and its
        // center index will be 2, and the half length will be 2.
        // And we want to ignore the starting "#", and let the starting index
        // point to 'a', that is 1.
        int startingIndex = maxPalindromeCenter - maxPalindromeLen + 1;

        // Transform to the index of the original string
        int originalStartIdx = startingIndex / 2;
        return s.substring(originalStartIdx, originalStartIdx + maxPalindromeLen);
    }

    public static void main(String[] args) {
        Solution finder = new Solution();
        assertEquals("", finder.longestPalindrome(""));
        assertEquals("aa", finder.longestPalindrome("aa"));
        assertEquals("a", finder.longestPalindrome("a"));
        assertEquals("aba", finder.longestPalindrome("daba"));
        assertEquals("aba", finder.longestPalindrome("abaa"));
        assertEquals("bccb", finder.longestPalindrome("abccbb"));
        assertEquals("bb", finder.longestPalindrome("cbbd"));
        assertEquals("bab", finder.longestPalindrome("babad"));
    }

    private static void assertEquals(Object expected, Object actual) {
        if (!Objects.equals(expected, actual)) {
            throw new AssertionError("Expecting " + expected + ", but see " + actual);
        }
    }
}