102953: [Atcoder]ABC295 D - Three Days Ago

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string $S$ consisting of digits. Find the number of pairs of integers $(l,r)$ satisfying all of the following conditions.

• $1 \le l \le r \le |S|$. ($|S|$ is the length of $S$.)
• The (contiguous) substring formed of the $l$-th through $r$-th characters of $S$ is happy.

Constraints

• $S$ is a string consisting of digits whose length is between $1$ and $5 \times 10^5$, inclusive.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print an integer representing the answer.

Sample Input 1

20230322

Sample Output 1

4

We have $S=$ 20230322.

Here are the four pairs of integers $(l,r)$ that satisfy the condition: $(1,6)$, $(1,8)$, $(2,7)$, and $(7,8)$.

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185

$S$ may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9

问题描述

字符串20230322可以重排为02320232，这是0232重复两次的结果。

同样地，一个由数字组成的字符串被认为是快乐的，当它可以重排为（或者已经是）一个字符串重复两次。

给你一个由数字组成的字符串$S$。找出满足以下所有条件的整数对$(l,r)$的数量。

• $1 \le l \le r \le |S|$。（$|S|$是$S$的长度。）
• $S$中由第$l$个到第$r$个字符组成的（连续）子串是快乐的。

约束条件

• $S$是一个长度在$1$到$5 \times 10^5$之间的由数字组成的字符串。

输入

输入数据从标准输入给出，格式如下：

$S$

输出

输出一个表示答案的整数。

样例输入1

20230322

样例输出1

4

我们有$S=$ 20230322。

满足条件的四个整数对$(l,r)$为：$(1,6)$，$(1,8)$，$(2,7)$和$(7,8)$。

样例输入2

0112223333444445555556666666777777778888888889999999999

样例输出2

185

$S$可以以0开头。

样例输入3

3141592653589793238462643383279502884197169399375105820974944

样例输出3

9