http://shirleyisnotageek.blogspot.com/2014/12/longest-palindromic-substring-dp-on.html
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.
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
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 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); }