a java O(n) solution with Manacher's algorithm that beats 99.8%


  • 0
    C

    I take @kingwolfofsky 's solution as as a reference, and give my java version solution.
    reference: https://discuss.leetcode.com/topic/3338/share-an-o-n-solution/8
    the key point of this solution is Manacher's algorithm. we can google it if we don't know it.

    public class Solution {
        // Manacher's ALGORITHM
        
        public String longestPalindrome(String s) {
            
            if (s==null || s.length() == 0) return "";
            
            int strLen = s.length();
            int externLen = (strLen << 1) + 1;
            char[] charArr = new char[externLen];
            
            int idx = 0;
            for (char ch : s.toCharArray()) {
                charArr[idx++] = '#';
                charArr[idx++] = ch;
            }
            charArr[idx] = '#';
            
            int[] dp = new int[externLen];
            int center=0, maxLen = 0;
            int pivot=0, maxPos=0;
            
            dp[0] = 1;
            for (int i=1; i < externLen; i++) {
                
                // this is key point to reach real O(n) time complex
                dp[i] = (maxPos > i)? Math.min(dp[(pivot << 1) - i], maxPos-i):1 ;
                
                while (i + dp[i] < externLen && i-dp[i] >= 0 && charArr[i+dp[i]] == charArr[i-dp[i]]) {
                    dp[i]++;
                }
                if (i+dp[i] > maxPos) {
                    maxPos = i+dp[i];
                    pivot = i;
                }
                if (dp[i] > maxLen) {
                    maxLen = dp[i];
                    center = i;
                }
            }
            
            return s.substring( (center - maxLen + 1)>>>1 , (center + maxLen - 1)>>>1);
        }
    }
    

Log in to reply
 

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