# Java O(n) solution, use Manacher's Algorithm

• I will not explain details of Manacher's algorithm because I think I can't do better than some of the online resources, e.g., I find the following video is quite good:

``````public int countSubstrings(String s) {

// Manacher's Algorithm
int sum = 0;

// boundary case
if (null == s || 0 == s.length()) return sum;
// extend the s with extra chars for Manacher's algorithm
char[] extendArr = preProcess(s);
// Manacher's algorithm to count palindromes
sum = manachers(extendArr);

return sum + s.length();
}

private char[] preProcess(String s) {

char[] arr = new char[s.length() * 2 + 3];

arr[0] = '@';
int index = 1;
for (; index < arr.length - 1; index ++) {
arr[index] = (index % 2 == 0) ? s.charAt(index / 2 - 1) : '#';

}
arr[index] = '&';
return arr;
}

private int manachers(char[] arr) {

int[] indicator = new int[arr.length];
indicator[0] = indicator[1] = 0;

int centre = 0;
int right = 0;
int mirr = 0;
int sum = 0;

for (int i = 1; i < arr.length - 1; i ++) {

mirr = 2 * centre - i;
if (i < right) indicator[i] = Math.min(indicator[mirr], indicator[right - i]);
while (arr[i + (indicator[i] + 1)] == arr[i - (indicator[i] + 1)])
indicator[i] ++;
sum += indicator[i] / 2;

if (i + indicator[i] > right) {
centre = i;
right = i + indicator[i];
}
}

return sum;
}
``````

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