/**
 * 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
 *
 */
// solution 1 (faster)
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;
    }
}

// solution 2
public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        String longest = new String();
        boolean[][] dp = new boolean[len][len];
        
        for(int i = len; i >= 0; i--) {
        	for(int j = i; j < len; j++) {
        		dp[i][j] = s.charAt(i) == s.charAt(j) && (j-i<3 || dp[i+1][j-1]);
            	if(dp[i][j] && ((j-i+1)>longest.length()))
                		longest = s.substring(i, j+1);
        	}
        }
        return longest;
    }
}

@@ -1047,34 +1047,32 @@
 lass Solution %7B%0A
-  
   public String 
@@ -1097,28 +1097,24 @@
 String s) %7B%0A
-    
     int len 
@@ -1131,20 +1131,16 @@
 ();%0A    
- 
-   
 String l
@@ -1166,20 +1166,16 @@
 ();%0A    
-   
- 
 boolean%5B
@@ -1214,21 +1214,13 @@
     
-    %0A  
+%0A
     
-  
 for(
@@ -1243,28 +1243,24 @@
 = 0; i--) %7B%0A
-    
     %09for(int
@@ -1279,28 +1279,24 @@
 len; j++) %7B%0A
-    
     %09%09dp%5Bi%5D%5B
@@ -1363,20 +1363,16 @@
         
-   
- 
 %09if(dp%5Bi
@@ -1419,20 +1419,16 @@
         
-    
 %09%09longes
@@ -1460,29 +1460,17 @@
     
- 
-   %09%7D%0A    
+%09%7D%0A
     %7D%0A
-    
     
@@ -1477,24 +1477,22 @@
 return longest;%0A
-  
   %7D%0A%7D%0A

Update 005.java