public static  String longestPalindrome(String s) {
        if(s.length() == 0 || s.length() == 1) return s;
        char[] sac = buildArrayWithCentinels(s);
        
        int[] MIRRORS = new int[sac.length];
        MIRRORS[0] = 0;
        
        int C = 0;//C
        int RB = 0;//rightBound
        int iMax = 0;
        
        for(int i = 1; i < sac.length; i++){
            //1. CAN USE MIRROR?
            int boost = 0;
            if(i < RB) boost = Math.min(MIRRORS[2 * C - i], RB - i);
            //2. EXPAND
            MIRRORS[i] = mirrorCount(sac, i, MIRRORS[i]);
            //3. NEW C
            if(i + MIRRORS[i] > RB){
                C = i;
                RB = i+MIRRORS[i];
            }
            //UPDATE MAX IF POSSIBLE
            if(MIRRORS[i] > MIRRORS[iMax]){
                iMax = i;
                RB = i + MIRRORS[i];
            }
        }
        //Build final result
        StringBuilder result = new StringBuilder();
        for(int i = iMax - MIRRORS[iMax]; i < iMax + MIRRORS[iMax] + 1; i++){
            result.append(sac[i]);
        }
        return result.toString().replace("#", "");
    }
    
    public static int mirrorCount(char[] sac, int index, int boost){
        int left = index - 1 - boost;
        int right = index + 1 + boost;
        int count = 0;
        while(left >= 0 && right < sac.length){
             if(sac[left] != sac[right]) break;
             count++;
            left--;
            right++;
        }
        return count+boost;
    }
    
    public static char[] buildArrayWithCentinels(String s){
    	char[] sa = s.toCharArray();
        char[] sac = new char[sa.length*2+1];//sa with centinels
        Arrays.fill(sac, '#');
        for(int i = 1, j = 0; i < sac.length; i+=2, j++){
            if(i % 2 != 0){
                sac[i] = sa[j];
            }
        }
        return sac;
    }