Training center
Check out Codility training tasks
Tasks Details
hard
Count the palindromic subwords of given string.
Task Score
100%
Correctness
100%
Performance
100%
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).

Complexity:

  • 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.
Solution
Programming language used C++
Total time used 21 minutes
Effective time used 21 minutes
Notes
not defined yet
Task timeline