Leetcode 5 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.

Solution 1: brute -force, iterate through the string. Find the max possible palindrome with current char in middle (odd palindrome) of left middle (even palindrome). It is not hat bad, most time just check one or two items to know the maximum.

 public class Solution {  
   public String longestPalindrome(String s) {  
     int n=s.length();  
     int max=0;  
     String res="";  
     for (int i=0; i<n; i++) {  
       int j=1;  
       while (i-j>=0 && i+j<n && s.charAt(i-j)==s.charAt(i+j)) j++;  
       if (2*j-1>max) {  
         max=2*j-1;  
         res=s.substring(i-j+1,i+j);  
       }  
       j=0;  
       while (i-j>=0 && i+j+1<n && s.charAt(i-j)==s.charAt(i+j+1)) j++;  
       if (2*j>max) {  
         max=2*j;  
         res=s.substring(i-j+1,i+j+1);  
       }  
     }  
     return res;  
   }  
 }  

Solution 2: When iterate through the string, find the max palindrome string end at the current char. The length of new max length can only be max+1 or max+2. Let us consider a string xxxkbkxxxxxxa... kbk is previous longest palindrome. We do not need to check String less than 3 as it will not be the new result. Can it be xxxxxa which is max+3? if so, we should have update in previous char already, as 4 charter string xxxx must be palindrome. So code as below. The real run time is not much better than brute force, especially when we find a long result, we keep checking long strings.

 public class Solution {  
   public String longestPalindrome(String s) {  
     int n=s.length();  
     if (n<2) return s;  
     int max=1;  
     String res=s.substring(0,1);  
     for (int i=1; i<n; i++) {  
       if (i-max-1>=0) {  
         String p=s.substring(i-max-1,i+1);  
         if (isPalin(p)) {  
           max+=2;  
           res=p;  
           continue;  
         }  
       }  
       String p=s.substring(i-max,i+1);  
       if (isPalin(p)) {  
         max++;  
         res=p;  
       }  
     }  
     return res;  
   }  
   private boolean isPalin(String p) {  
     int i=0;  
     int j=p.length()-1;  
     while (i<j) {  
       if (p.charAt(i++)!=p.charAt(j--)) return false;  
     }  
     return true;  
   }  
 }