[AdditionalFile5517.zip](file://AdditionalFile5517.zip?type=additional_file)

#5517. 「PA 2019 Final」Łamana 2

标签: 传统 | 时间限制: 500 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2019 Final Łamana 2

Basia 有一个字符串 $s$，其中的每个字符是英文字母表前 $16$ 个小写字母之一。她将字符串中的每个字符替换为向右或向上的箭头，并需满足条件：相同的字母必须替换为相同的箭头。例如，字符串 banan 可以替换为 $\uparrow \uparrow \rightarrow \uparrow \rightarrow$ 或 $\uparrow \uparrow \uparrow \uparrow \uparrow$，但不能替换为 $\rightarrow \rightarrow \rightarrow \uparrow \rightarrow$，因为这会要求将两个字母 a 替换为不同的箭头。

Basia 将使用得到的箭头序列绘制一条折线。她会从点 $(0, 0)$ 开始，将铅笔按箭头方向依次移动 $n$ 次，每次向右或向上移动 $1$ 个单位。

绘图的结果定义为折线与 X 轴之间区域的面积。形式上，该区域是所有点 $(x, y)$ 的集合，其中 $y \geq 0$，且存在点 $(x, y^{\prime})$ 属于折线且满足 $y^{\prime} \geq y$。

Basia 的绘图结果的最大可能值是多少？

输入格式

输入的唯一一行包含一个单词 $s$ $(1 \leq |s| \leq 300000)$，由小写英文字母 a 到 p（共 $16$ 个可能的字符）组成。

输出格式

输出一个整数，表示按照规则将字母替换为箭头后，绘图结果的最大可能面积。

样例 1

输入

banan

输出

5

字符串 banan 的最佳替换为 $\uparrow \uparrow \rightarrow \uparrow \rightarrow$。此时折线下方区域的面积为 $5$。

样例 2

输入

abcdefghijklmnopaaaa

输出

90

字符串 abcdefghijklmnopaaaa 存在两种最佳替换方案，每种方案的面积均为 $90$。