Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

#### CountPalindromicSlices

Count the palindromic subwords of given string.

In this problem we consider only strings consisting of lower-case English letters (a−z).

A string is a palindrome if it reads exactly the same from left to right as it does from right to left. For example, these strings are palindromes:

• aza
• abba
• abacaba

These strings are not palindromes:

• zaza
• abcd

Given a string S of length N, a slice of S is a substring of S specified by a pair of integers (p, q), such that 0 ≤ p < q < N. A slice (p, q) of string S is palindromic if the string consisting of letters S[p], S[p+1], ..., S[q] is a palindrome. For example, in a string S = abbacada:

• slice (0, 3) is palindromic because abba is a palindrome,
• slice (6, 7) is not palindromic because da is not a palindrome,
• slice (2, 5) is not palindromic because baca is not a palindrome,
• slice (1, 2) is palindromic because bb is a palindrome.

Write a function

class Solution { public int solution(String S); }

that, given a string S of length N letters, returns the number of palindromic slices of S. The function should return −1 if this number is greater than 100,000,000.

For example, for string S = baababa the function should return 6, because exactly six of its slices are palindromic; namely: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..20,000];
• string S is made only of lowercase letters (az).