Java easy to understand O(n^2) solution


  • 0
    M

    Since I don't have a full grasp on Manacher's algorithm yet, I wanted to take the same concept to implement O(n^2) and build onto it. I think it's pretty straightforward, I like being able to have access to an array with the max length at each position. I'd like to not have to inject all the extra characters. Do you know of any improvements that could be made without implementing Manacher's algorithm?

    class Solution {
        public String longestPalindrome(String s) {
            int dLength = 2 * s.length() + 1;
            int[] counts = new int[dLength];
            StringBuilder ds = new StringBuilder(s);
            for(int i = 0; i < counts.length; i++){
                if(i < dLength && i % 2 == 0)ds.insert(i, '#');
                counts[i] = 0;        
            }
            int max = 0;
            int maxIndex = 0;
            for(int i = 1; i < counts.length - 1; i++){
                int size = getPalindromeSizeAtIndex(i, ds.toString());
                counts[i] = size;
                if(size > max){
                    max = size;
                    maxIndex = i;
                }
            }
            return ds.substring(maxIndex - max, maxIndex + max).replace("#", "");
        }
       
        public int getPalindromeSizeAtIndex(int i, String s){
            int counter = 1;
            while(counter < s.length() + 1 / 2){
                if(i - counter == -1 || i + counter == s.length())return counter -1;
                char ls = s.charAt(i - counter);
                char rs = s.charAt(i + counter);
                if(ls != rs)return counter -1;
                counter++;
            }
            return counter;
        }
    }
    

Log in to reply
 

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