题目背景

2025 年 03 月 GESP C++ 七级编程第 2 题

题目描述

小 A 有一个仅包含小写英文字母的字符串 $S$。

如果一个字符串能通过每次删去其中两个相同字符的方式变为空串，则称它是可以被等价消除的。请计算 $S$ 有多少个子串可以被等价消除。

字符串 $Sprime$ 是 $S$ 的子串，当且仅当删去 $S$ 的某个可以为空的前缀和某个可以为空的后缀后，可以得到 $Sprime$。

输入格式

第一行输入正整数 $|S|$，表示字符串长度。 第二行输入一个仅包含小写英文字母的字符串 $S$。

输出格式

输出一行一个整数，表示可以被等价消除的子串数量。

7
aaaaabb

9

9
babacabab

2

数据范围与提示

• 对于 $20\%$ 的测试点，保证 $S$ 中仅包含 a 和 b 两种字符。
• 对于另外 $20\%$ 的测试点，保证 $1 \le |S|\le 2000$。
• 对于全部测试点，保证 $1 \le |S|\le 2 imes 10^5$。

来源

GESP 2025 年 03 月 C++ 七级 T2