Short O(n^2) & constant space Java solution


  • 0
    M
    public class Solution {
    	 public String longestPalindrome(String s) {
             int[] max = new int[]{0,0};
             
             for(int i = 0; i < s.length(); i++)
                 max = maxlen(maxlen(max, expandPalindrome(s, i, i)), i + 1 < s.length()? expandPalindrome(s, i, i+1):max);
             
             return s.substring(max[0], max[1]+1);
         }
         
         public int[] expandPalindrome(String s, int left, int right) {
             while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                 left--;
                 right++;
             }
             return new int[]{left+1, right-1};
         }
         
         private int[] maxlen(int[] i1, int[] i2) {
             return i1[1] - i1[0] > i2[1] - i2[0]? i1 : i2; 
         }
    }
    

Log in to reply
 

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