Longest Palindromic Substring - DP & O(n) solution

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.

The first thought when seeing keyword "longest" and "substring" would be DP! Yep, and the solution is accepted.

public class LongestPalindrome {
    public String longestPalindrome(String s) {
     if (s == null || s.length() == 0)
      return "";
     String rst = s.substring(0,1);
     int maxSubstring = 1;
     boolean[][] palindrome = new boolean[s.length()][s.length()];
     for (int i = 0; i < s.length(); i++) {
      palindrome[i][i] = true;
     }
     for (int len = 1; len < s.length(); len++) {
      for (int i = 0; i + len < s.length() ; i++) {
       if (len < 2) {
        palindrome[i][i + len] = (s.charAt(i) == s.charAt(i + len));
       }
       else {
        palindrome[i][i + len] = palindrome[i + 1][i + len - 1] && (s.charAt(i) == s.charAt(i + len));
       }
       if (palindrome[i][i + len] && (len + 1 > maxSubstring)){
        maxSubstring = len + 1;
        rst = s.substring(i, i + len + 1);
       }
      }
     }
     return rst;
    }
}

However, as we know, 2D DP requires O(n^2) complexity. Naturally we will ask, can we do better?
Of course we can! Otherwise what's this post about?

The complete explanation of this O(n) solution, which is called, Manacher's Algorithm can be found here. I will just simplify it based on my understanding.

So consider we have a string s = "aabab". How can we check every substring using iteration? We need to check "aa", "aab", "aaba", "aabab", then "aba" ... and so on. Then this will be O(n^2), we are not doing anything better. But, what if we add something into the string:

# a # a # b # a # b #
0   1  2  3  4   5  6   7  8   9  10

Well, whatever symbol you would like to use is fine. The point is, now we double the length of the string, and every substring of s is symmetric in the new string. If we want to check "aa", it is symmetric against "#", "aba" is symmetric against "b". Thus, by iterate through the new string, we can check every substring of s in linear time.

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return "";
        int maxSubstring = 1;
        String rst = s.substring(0, 1);
        for (int i = 1; i <= 2 * s.length() - 1; i++) {
            int count = 1;
            while (i - count >=  0 && i + count <= 2 * s.length() && get(s, i - count) == get(s, i + count)) {
                count++;
            }
            //Note that since "#" always equals "#", we will have an extra count for each substring
            count--;
            if (count > maxSubstring) {
                maxSubstring = count;
                rst = s.substring((i - count) / 2, (i + count) / 2);
            }
        }
        return rst;
    }
        private char get(String s, int index) {
            if (index % 2 == 0)
                return '#';
            else
                return s.charAt(index / 2);
        }
}

Ah, beautiful solution! :)