Problem Brief

Count Palindromic Substrings

FULLTIMEOA

A string S is called palindrome if it reads the 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":

1) ellolle
2) ll, ll - note that these are two distinct substrings that only happen to be equal
3) lol and lloll
4) And, of course, each letter can be considered a palindrome - all 8 of them.

Write a function that, given a string S (that only consists of lowercase English letters), counts how many different ways are there to pick a palindrome substring from S.

1Example 1

Input

s = "hellolle"

Output

Explanation

N/A

2Example 2

Input

s = "wowpurerocks"

Output

Explanation

N/A

Draft autosaves locally

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

Input

"hellolle"

Output