public class Solution {
public static int numberOfPalindromicSubstrings(String S) {
// Conversion of string into required form
char[] str = new char[2 * S.length() + 3];
str[0] = '@';
str[1] = '#';
str[str.length - 1] = '$';
int index = 2;
for (char c : S.toCharArray()) {
str[index++] = c;
str[index++] = '#';
}
int[] palindromicLength = new int[str.length];
int center = 0, right = 0;
for (int i = 1; i < palindromicLength.length - 1; ++i) {
// Finding mirror element
int mirror = i - 2 * (i - c);
// If i is within range
if (i < right)
palindromicLength[i] = Math.min(right - i, palindromicLength[mirror]);
// Expanding about center, using any min length we have
while (str[i + palindromicLength[i] + 1] == str[i - palindromicLength[i] - 1])
palindromicLength[i]++;
// If range of palindrome of i, is greater than range of "main" palindrome
if (i + palindromicLength[i] > right) {
center = i;
right = i + palindromicLength[i];
}
}
int ans = 0;
for (int length : palindromicLength)
ans += (length + 1) / 2;
return ans;
}
}