Very simple clean java solution


  • 216
    J

    The performance is pretty good, surprisingly.

    public class Solution {
    private int lo, maxLen;
    
    public String longestPalindrome(String s) {
    	int len = s.length();
    	if (len < 2)
    		return s;
    	
        for (int i = 0; i < len-1; i++) {
         	extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
         	extendPalindrome(s, i, i+1); //assume even length.
        }
        return s.substring(lo, lo + maxLen);
    }
    
    private void extendPalindrome(String s, int j, int k) {
    	while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
    		j--;
    		k++;
    	}
    	if (maxLen < k - j - 1) {
    		lo = j + 1;
    		maxLen = k - j - 1;
    	}
    }}

  • 3
    A

    Why are you not required to handle case like "aaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaa"? my programming is just like you but cannot pass this case.


  • 2
    A

    This is my code:

    public class Solution {

    public String longestPalindrome(String s) {
    	String sub = "";
    	if(s.length()==1||s==null){
    		return s;
    	}
    	if(s.length()==2){
    		if(s.charAt(0)==s.charAt(1)){
    			return s;
    		}else {
    			return s.substring(1);
    		}
    	}
        for(int i=2;i<s.length();i++){      	
        	if(s.charAt(i)==s.charAt(i-2)){
            	int j, k;
            	for(j=i-2, k=i;j>=0&&k<s.length();j--, k++){
            		if(s.charAt(j)!=s.charAt(k)){
            			break;
            		}
            	}
            	if(sub.length()<s.substring(j+1, k-1).length()){
            		if(k-1==s.length()-1){
            			sub=s.substring(j+1);
            		}else {
            			sub=s.substring(j+1, k-1);
    				}
            			
            	}       		
            }        		
        	
        }
        for(int i=1;i<s.length();i++){
        	if(s.charAt(i)==s.charAt(i-1)){
        		int j, k;
        		for(j=i-1, k=i;j>=0&&k<s.length();j--, k++){
        			if(s.charAt(j)!=s.charAt(k)){
        				break;
        			}
        		}
        		if(sub.length()<s.substring(j+1, k-1).length()){
        			if(k-1==s.length()-1){
        				sub=s.substring(j+1);
        			}else {
        				sub=s.substring(j+1, k-1);
        			}
        		}
        	}
        	
        }
        return sub;
    }
    

    }


  • 6
    Y

    Correct me if I'm wrong, but your solution would have worst case performance of O(n^2), right? But I guess when each of the palindrome string centered at each character is short, we will have O(n*len) on average. Just wondering what you think.


  • 0

    good solution


  • 4
    A

    Is this time complexity O(n^2) where n is the length of the input string??


  • 4
    F

    @yfcheng @atwoodwang0918 Yes, the worst case is O(n^2), just think in case of a string with repeating same character, "aaaaaaaaaaaaa". extendPalindrome will always extend to the boundaries.


  • 0
    A

    Hi, I am wonder does the worse case should be O(NlogN) rather than O(N^2) . Because for extendPalindrome it worse case is start on center, and left pointer keep moving until -1, right pointer keep move until s.length(). Should extendPalindrome be O(log N) rather than O(N)?


  • 1
    J

    Should the running time for my code the same?? Why cannot pass "aaaaa.."?

    public class Solution {
    /*
     * Exists longest unique Palindrome
     */
     public String longestPalindrome(String s) {
         int[][]matrix = new int[s.length()][s.length()];
    	 int max = 0;;
    	 int index=0;
         for(int i = 0; i < s.length(); i++){
        	 for(int j = s.length()-1; j>=0; j--){
        		 matrix[i][j] = 1;
        		 if(s.charAt(i)==s.charAt(j)){
        			 if(i>0&&j<s.length()-1){
        				 matrix[i][j]=matrix[i-1][j+1]+1;
        			 }
        			 if(max<matrix[i][j]){
        				 max = matrix[i][j];
        				 index = i;
        			 }
        			 
        		 }
        	 }
         }
    	 return s.substring(index-max+1, index+1);
        }
    

    }


  • 0
    L

    extendPalindrome should be O(N),imagine the worst case i = mid,and the input is "aaaaaaa",left pointer keep moving until -1, right pointer keep move until s.length(),one by one,is linear.the complexity is O(N/2)~O(N).


  • 2
    L

    I use DP method, which is also O(n2) time complexity like yours. But the actual performance is far more worse than this method. I believe it's because of the test case.

    Any suggestion is appreciated. I use isPalindrome[i][j] representing if s.substring(i, j + 1) is palindrome and isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j)

    public class Solution {
        public String longestPalindrome(String s) {
            if (s == null || s.length() < 2) {
                return s;
            }
            char[] c = s.toCharArray();
            boolean[][] isPalindrome = new boolean[c.length][c.length];
            int start = 0;
            int end = 0;
            int counter = 0;
            int preCounter = 0;
    
            // basic case for only one character
            for (int i = 0; i < isPalindrome.length; i++) {
                isPalindrome[i][i] = true;
                start = i;
                end = i;
            }
    
            // basic case for only two characters
            for (int i = 0; i < isPalindrome.length - 1; i++) {
                if (c[i] == c[i + 1]) {
                    isPalindrome[i][i + 1] = true;
                    start = i;
                    end = i + 1;
                } else {
                    isPalindrome[i][i + 1] = false;
                }
            }
            
            // for substring from index a to b, i == b - a
            for (int i = 2; i < isPalindrome.length; i++) {
                counter = 0; // uesd for check is no new palindrome for a longer substring for better performance
                // j is the starting point of a substring
                for (int j = 0; j < isPalindrome.length -i; j++) {
                    int index = j + i;
                    // check is 2 characters shorter substring is palindrome and if character on two ends is equal
                    if (isPalindrome[j + 1][index - 1] && c[j] == c[index]) {
                        isPalindrome[j][index] = true;
                        counter++;
                        start = j;
                        end = index;
                    } else {
                        isPalindrome[j][index] = false;
                    }
                }
                if (counter == 0 && preCounter == 0) {
                    break;
                }
                preCounter = counter;
            }
            
            return s.substring(start, end + 1);
        }
    }
    

  • 2
    C

    very good solution.
    easy to understand.
    well, why not add a condition statement before call the extendPalindromic func.
    like

     if(s.charAt(i)==s.charAt(i+1))
                    extendPalindromic(s,i, i+1); // if the length is even.
    

    1ms faster.


  • 1
    I

    @cuteonion What about the situation which the palindrome is 7 'a's? Also match your judgement but it is odd.


  • 0
    J

    Any idea how this code gets 13ms in java? It seems like a pretty straight forward approach. I ran the exact same code in python and get 1400ms instead.


  • 2
    P

    @cuteonion 1ms faster I think doesn't prove anything. Though your idea is very good.


  • 0
    P

    @lisen hi, I don't know

     for (int i = 2; i < isPalindrome.length; i++) {
                counter = 0;
                for (int j = 0; j < isPalindrome.length -i; j++) {
                    int index = j + i;
                    if (isPalindrome[j + 1][index - 1] && c[j] == c[index]) {
                        isPalindrome[j][index] = true;
                        counter++;
                        start = j;
                        end = index;
                    } else {
                        isPalindrome[j][index] = false;
                    }
                }
                if (counter == 0 && preCounter == 0) {
                    break;
                }
                preCounter = counter;
            }
    
    

    means. Could you put some comments on it? Thanks.


  • 0
    L

    @Piers I have updated my code with comments.


  • 11

    Very efficient solution even O(N^2) in the worst case. Here is a variation of yours without global variable:

        public String longestPalindrome(String s) {
            int max = 0, idx = 0;
            for (int i = 0; i < s.length(); i++) {
                int len1 = extend(s, i, i), len2 = extend(s, i, i + 1);
                if (max < Math.max(len1, len2)) {
                    idx = (len1 > len2) ? (i - len1 / 2) : (i - len2 / 2 + 1);
                    max = Math.max(len1, len2);
                }
            }
            return s.substring(idx, idx + max);
        }
        
        private int extend(String s, int i, int j) {
            for (; i >= 0 && j < s.length(); i--, j++)
                if (s.charAt(i) != s.charAt(j))
                    break;
            return j - i - 2 + 1; // 2 means current two unmatched char
        }
    

    ps: or could we get more readability by trade-off like this?

        public String longestPalindrome(String s) {
            String max = "";
            for (int i = 0; i < s.length(); i++) {
                String s1 = extend(s, i, i), s2 = extend(s, i, i + 1);
                if (s1.length() > max.length()) max = s1;
                if (s2.length() > max.length()) max = s2;
            }
            return max;
        }
        
        private String extend(String s, int i, int j) {
            for (; 0 <= i && j < s.length(); i--, j++) {
                if (s.charAt(i) != s.charAt(j)) break;
            }
            return s.substring(i + 1, j);
        }
    

  • 0
    C

    good solution


  • 0
    C

    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k))
    this sentens has the risk of "java.lang.StringIndexOutOfBoundsException", right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.