Longest Palindromic Substring

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".

Challenge:

O(n2) time is acceptable. Can you do it in O(n) time.

Solution:

We could convert "abcdzdcab" to "#a#b#c#d#z#d#c#a#b#". Then we iterate through each value and expand it with two pointers: left and right, we need to return the two pointers with maximum length.

Code:

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int n = s.length();
        int extendN = 2 * n + 1;
        int start = 0;
        int end = -1;
        for (int i = 1; i <= extendN; i++) {
            int left = i - 1;
            int right = i + 1;
            while (left > 0 && right <= extendN) {
                if (get(s, left) == get(s, right)) {
                    left--;
                    right++;
                } else {
                    break;
                }
            }
            left++;
            right--;
            if (right - left > end - start) {
                start = left;
                end = right;
            }
        }
        return s.substring(start / 2, end / 2);
    }

    private char get(String s, int index) {
        if (index % 2 == 1) {
            return '#';
        } else {
            return s.charAt((index - 1) / 2);
        }
    }
}