My short simple Java solution O(n^2)


  • 2
    S

    The idea here is to keep track of the left and right of the string and slide a window rightward until we find a palindrome then move the left marker over one when we get to the end of the string and try again. There's an optimization to skip checking any strings that are shorter than the currently longest palindrome.

    public class Solution {
        public String longestPalindrome(String s) {
            if (s.length()==0 || s.length()==1) return s;
            char[] arr=s.toCharArray();
            int longest=0;
            int saveL=0;
            int saveR=0;
            for(int l=0;l<arr.length;l++) { 
                for(int r=l;r<arr.length;r++) {
                    int palLen=r-l+1;
                    if (palLen < longest) { continue; }
                    int p=l;
                    int q=r;
                    while (q>=p) {
                        if (!(arr[p]==arr[q])) break;
                        p++;
                        q--;
                    }
                    if (q<p && palLen>longest) {
                        longest=palLen;
                        saveL=l;
                        saveR=r;
                    }
                }
            }
            return s.substring(saveL,saveR+1);
        }
    }

Log in to reply
 

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