Given a string, output the number of nice pairs of special substrings. A special substring is a string that reads the same forwards and backwards. A nice pair of substrings is a pair of substrings that has the following property: after you remove the first substring from the string, you can still remove the second substring from the string (note that neither substring should be contained in the other to be nice).
Input Specification
The first and only line of input will contain a string consisting of lowercase letters. The length of the string will be at least and at most
characters long.
Output Specification
Output the number of nice pairs of special substrings.
Sample Input 1
aba
Sample Output 1
3
Sample Input 2
aaayyylllmmmaaaooo
Sample Output 2
570
Comments
https://codeforces.com/blog/entry/451 Problem E
Remember, it's not called a very very original problem for nothing.
Can both substrings in a pair of substrings be the same? If you remove the first substring, are you removing all occurrences of it in the string, or just one? For example, in Sample 2 is 'aaa' and 'aaa' a possible pair?
Yes, 'aaa' and 'aaa' is a possible pair. You only remove that single instance of the substring.