Antipalindrome

Interview

Time limit1sMemory limit1024 MB

Summary

Count the contiguous substrings of the given word that contain no palindrome of length 2 or more.

Level: Medium5 of 10
Topics: String, Sliding window, Two pointers
Solved: No attempts yet

Problem

A palindrome is a word that reads the same forwards and backwards, such as kajak or anna. In this problem, a palindrome must have at least 2 characters. An antipalindrome is a word that contains no palindrome as a contiguous substring. For example, bajtek and bajtocja are antipalindromes, while kajak and olimpiada are not.

Bajtynka does not like palindromes. She wrote a word on paper to use as her nickname in an online game, but she suspects it contains a palindrome, which would spoil her mood. So she decides to cut off some (possibly empty) prefix from the front and some (possibly empty) suffix from the end, so that the remaining part, which must not be empty, is an antipalindrome. There are many ways to do this. How many exactly?

Write a program that counts the ways to cut a prefix and a suffix from the word so that the remaining non-empty part is an antipalindrome.

Input

The first and only line contains a non-empty string of lowercase English letters, Bajtynka's word. Its length does not exceed 100,000 characters.

Output

The first and only line contains one non-negative integer: the number of distinct ways to cut the word so that the remaining part is a non-empty antipalindrome. Two ways are different if they remove a different number of characters from the front or a different number from the back.

Examples3

Example 1
Input
```
ababc
```
Expected output
```
10
```
Example 2
Input
```
mocowocom
```
Expected output
```
21
```
Example 3
Input
```
abba
```
Expected output
```
6
```