Count Palindromic Substrings with Character Frequency Constraint

Given a string composed of lowercase letters, count the number of intervals \([l,r]\) such that the substring represented by this interval is a palindrome and every character in the substring appears at most \(2\) times. A substring is a contiguous sequence of characters. A palindrome is a string that reads the same forwards and backwards. In other words, for a substring \(s[l..r]\), it must satisfy:

\(s[l..r] = reverse(s[l..r])\)

and for each character \(c\) in \(s[l..r]\), the frequency constraint is:

\(\text{count}(c) \leq 2\)

inputFormat

The input consists of a single line containing a non-empty string of lowercase letters.

outputFormat

Output a single integer representing the number of intervals \([l,r]\) for which the substring is a palindrome and each character appears at most \(2\) times.

sample

aba

4