Longest Palindromic Substring

Problem

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Example

Given the string = "abcdzdcab", return "cdzdc".

Code - Java

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        char[] a = s.toCharArray();
        char[] b = new char[a.length * 2 + 3];
        b[0] = '$';
        b[a.length * 2 + 1] = '#';
        b[a.length * 2 + 2] = '&';
        for (int i = 0; i < a.length; i++) {
            b[2 * i + 1] = '#';
            b[2 * i + 2] = a[i];
        }

        int[] p = new int[b.length];
        int index = 1;
        int maxLength = 0;
        for (int i = 2; i < p.length - 2; i++) {
            if (index + p[index] > i) {
                // i's mirror point
                int j = index - (i - index);
                p[i] = Math.min(p[j], index + p[index] - i);
            } else {
                p[i] = 1;
            }

            // matching and extending p[i]
            while (b[i + p[i]] == b[i - p[i]]) p[i]++;

            if (p[i] > p[index]) {
                index = i;
            }
        }

        String result = "";
        for (int i = index - p[index] + 1; i <= index + p[index] - 1; i++) {
            if (b[i] != '#') {
                result += b[i];
            }
        }

        return result;
    }
}