Longest Palindromic Substring

Source

• lintcode: 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.

Java

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        //从中间往两边扩散
        String result="";
        for(int i=0; i<s.length(); i++){
            String res = calculatePalindorm(s, i, i);
            if(res.length()>result.length()){
                result =res;
            }
            res = calculatePalindorm(s, i, i+1);
            if(res.length()>result.length()){
                result =res;
            }    
        }
        return result;
    }

    public String calculatePalindorm(String s, int i, int j){
        while(i>=0 && j<s.length()){
            char a = s.charAt(i);
            char b = s.charAt(j);
            if(a==b){
                i--;
                j++;
            }
            else{
                return s.substring(i+1, j);
            }
        }
        return s.substring(i+1, j);
    }
}