Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
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
  • abacada

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 consists only of lowercase letters (az).
Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.