Problem Brief

Count Different Palindrome Substrings

FULLTIMEOA

A string S is considered palindrome if it reads same way if spelled backwards, for example "nolemonnomelon", "ASANtaLivedAsAdeviLatNASA".

Any non-empty string has substrings that are palindromes. For example, in the string S = "hellolle", there are many of such "subpalindromes":

ellolle

ll, ll - note that these are two distinct substrings that only happen to be equal.

lol and lloll

And each single letter can be considered a palindrome - 8 of them.

Please write a function that, given a string S (only contains lowercase letters), returns number of different ways are there to pick a palindrome substring fro mS.

1Example 1

Input

s = "hellolle"

Output

Explanation

Output 13.

2Example 2

Input

s = "wowpurerocks"

Output

Explanation

each letter + "wow" + "rer"

Draft autosaves locally

public int countDifferentPalindromeSubstrings(String s) {
  // write your code here
}

Input

"hellolle"

Output