Substrings
/

## Algorithms, Basic Programming, String Manipulation

Problem
Editorial
Analytics

You have a string S, but you like only special strings. So, you have to calculate the total number of special substrings in S.

A string T, of length L, is called special string, if either of the following property holds:

1. All characters of the string T are same. for example, $aaa$
2. The string has an odd length (i.e, L is odd) and all characters of T are same except the middle character, for example, $aabaa$.

Count the total number of special substrings in S.

Input constraints:

• String S contains only lower-case English alphabets.
• $1 \le|S| \le10^{6}$, where |S| is the length of string S.
SAMPLE INPUT
aba

SAMPLE OUTPUT
4

Explanation

S="aba"
Then there are 4 special substrings: {"a", "b", "a", "aba"}

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...