Training center
Check out Codility training tasks
Tasks Details
Count the palindromic subwords of given string.
Task Score
Task description

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

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).

Assume that:

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


  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N) (not counting the storage required for input arguments).
Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Programming language used C++
Total time used 21 minutes
Effective time used 21 minutes
not defined yet
Task timeline