Java Solution(99.03%)- O(N) easy to understand


  • 0
    P

    This solution is based on Manacher's algo.

    // Solution
    public class Solution {
    /*
    Solving the code using Manacher's Algo.
    /
    public String longestPalindrome(String s)
    {
    // Declare Variables
    int index = 0; // index for the outer loop
    int max_length = 0, center = 0; // store the max values
    int length = s.length();
    int i = 0; // for inner loops
    if(s.length() == 0) return s; // null string
    char[] a = new char[2
    length + 1]; // Convert string From abccba to $a$b$c$c$b$a$// this makes all palindromes of odd length
    int temp_length = 2*length+1;
    int[] palLength = new int[temp_length]; // Store the length of palindrome at the index equal to the center of the pallindrome
    //~Declare Variables

         // fill the temp array -- abccba to $a$b$c$c$b$a$
         for(i = 0; i < length; i++)
         {
             a[2*i+1] = s.charAt(i);
         }
         palLength[0] = 1;
         // outer Loop 
         while(index < temp_length)
         {
             int currentlength = longestPalindrome_withcentre(a,index,palLength[index]);
             palLength[index] = currentlength;
             if(currentlength > max_length)
             {
                 center = index;
                 max_length = currentlength;
             }
             // We can skip a few indexs -- Manacher's Algo...
             if(index + currentlength/2 == temp_length) break; 
             // find the next centre
             for(i = 1; i <= currentlength/2 - 1; i++)
             {
                 palLength[index + i] = palLength[index - i];
                 if(palLength[index - i]/2 + i == currentlength/2)
                 {
                     // Only this case is not to be skipped.
                     break;
                 }
                 if(palLength[index - 1]/ 2 + i > currentlength/2)
                 {
                   palLength[index+i] = (currentlength/2 - i)*2 + 1;
                 }
            }
            // skip indexes.
            index += i;
         }
         int startpoint = center - max_length/2;
         return s.substring(startpoint/2,startpoint/2 + max_length/2);
    }
    public int longestPalindrome_withcentre(char[] s, int index, int minLength)
    {
        int length_even = minLength;
        int left_ptr = index - 1 - minLength/2;
        int right_ptr = index + 1 + minLength/2;
        while(left_ptr >= 0 && right_ptr < s.length)
        {
            if(s[left_ptr] != s[right_ptr])
            break;
            length_even += 2;
            left_ptr--;
            right_ptr++;
        }
        return length_even;
    }
    

    }


Log in to reply
 

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