Easy java solution with O(1) space and O(n^2) time


  • 19
    J

    The basic idea is to traverse all the palindromes with its pivot range from the first char of string s to the last char of string s (consider both even length and odd length situation). Use StringBuilder to minimize the space complexity. Here is the code, feast yourself:

    public class Solution {
    StringBuilder longest = new StringBuilder("");
    
    public String longestPalindrome(String s) {
        if (s.length() <= 1) return s;
        
        for (int i = 0; i < s.length(); i++) {
            expand(s, longest, i, i); //odd
            expand(s, longest, i, i + 1); //even
        }
        
        return longest.toString();
    }
    
    private void expand(String s, StringBuilder longest, int i, int j) {
        while (i >= 0 && j < s.length()) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j - i + 1 > longest.length()) {
                    longest.delete(0, longest.length());
                    longest.append(s.substring(i, j + 1));
                }
                i--;
                j++;
            }
            else
                break;
        }
    }
    

    }


  • 15
    B

    Thanks, very easy, a modified version without StringBuiler, accepted with 214 ms.

        public class Solution {
        private int maxLength = 1;
        private int maxIndex = 0;
        public String longestPalindrome(String str) { //O(N^2), space O(1)
            int length = str.length();
            for (int i=0; i<length; i++) {
                // find longest odd palindrome with center i
                findPalindrome(str, length, i, 0);
                // find longest even palindrome with center i
                findPalindrome(str, length, i, 1);
            }
            return str.substring(maxIndex, maxIndex+maxLength);
        }
    
        private void findPalindrome(String str, int length, int i, int shift) {
          int left = i;
          int right= i+shift;
          while (left >= 0 && right < length && str.charAt(left) == str.charAt(right)) {
            if ((right - left + 1) > maxLength) {
              maxLength = right - left + 1;
              maxIndex = left;
            }
            left--;
            right++;
        }
       }
    
      }
    

  • 0
    S

    Thanks for your answer, but the space is O(N).


  • 0
    F

    it is not a good idea to manage the stringbuilder here, the "delete" operation makes your complexity goes to O(n^3)


  • 0
    T
    public String longestPalindrome(String s) {
    	int index = 0;
    	int length = 1;
    	for (int i = 0; i < s.length(); i++) {
    		// 类型1的回文 baab 形式
    		if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
    			int templen = 2;
    			int tempindex = i;
    			for (int m = i - 1, n = i + 2; m >= 0 && n < s.length(); m--, n++) {
    				if (s.charAt(m) == s.charAt(n)) {
    					templen += 2;
    					tempindex = m;
    				} else {
    					break;
    				}
    			}
    
    			if (templen > length) {
    				length = templen;
    				index = tempindex;
    			}
    		} 
    		if (i + 1 < s.length() && i-1 >=0 && s.charAt(i-1) == s.charAt(i + 1)) {
    			int templen = 1;
    			int tempindex =i-1 ;
    			for(int m=i-1, n =i+1; m >= 0 && n < s.length(); m--, n++ ) {
    				if (s.charAt(m) == s.charAt(n)) {
    					templen += 2;
    					tempindex = m;
    				} else {
    					break;
    				}
    			}
    			
    			if (templen > length) {
    				length = templen;
    				index = tempindex;
    			}
    		} 
    	}
    	
    	return s.substring(index, length+index);
    }

  • 0
    C

    feel not good to define the maxLength and maxIndex to be a private variable... It might cause synchronization problem when this object is invoked by multiple instances.


  • 0
    A

    They are instance variables so why would they have synchronization issues ?


  • 0
    W

    This solution works better than upper solution.


Log in to reply
 

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