/**
 * 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.
 * @author Jun
 *
 */

public class Solution {
    public String longestPalindrome(String s) {
      if(s == null)  return s;
      int len = s.length();
      String longest = new String();
      for(int i = 0; i < len; i++) {
        if (i+1<len && s.charAt(i) == s.charAt(i+1))
            longest = palindromeSubstring(s, longest, i, i+1);
        longest = palindromeSubstring(s, longest, i, i);
      }
      return longest;
    }
    
    private static String palindromeSubstring(String s, String currentLongest, int start, int end) {
    	while(start >=0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
        start--; 
        end++;
      }
      start++; 
      if(end-start > currentLongest.length())
        return s.substring(start, end);
      else
      	return currentLongest;
    }
}

@@ -201,16 +201,38 @@
 %0A *%0A */%0A
+// solution 1 (faster)
 %0Apublic 
@@ -1016,8 +1016,535 @@
     %7D%0A%7D%0A
+%0A// solution 2%0Apublic class Solution %7B%0A    public String longestPalindrome(String s) %7B%0A        int len = s.length();%0A        String longest = new String();%0A        boolean%5B%5D%5B%5D dp = new boolean%5Blen%5D%5Blen%5D;%0A        %0A        for(int i = len; i %3E= 0; i--) %7B%0A        %09for(int j = i; j %3C len; j++) %7B%0A        %09%09dp%5Bi%5D%5Bj%5D = s.charAt(i) == s.charAt(j) && (j-i%3C3 %7C%7C dp%5Bi+1%5D%5Bj-1%5D);%0A            %09if(dp%5Bi%5D%5Bj%5D && ((j-i+1)%3Elongest.length()))%0A                %09%09longest = s.substring(i, j+1);%0A        %09%7D%0A        %7D%0A        return longest;%0A    %7D%0A%7D%0A

Update 005.java