题解：B. 删除第一个或第二个字母

问题重述

给定长度为 $n$ 的字符串 $s$，可以执行两种操作任意多次：

1. 删除当前字符串的第一个字符；
2. 删除当前字符串的第二个字符。

求所有可能得到的 不同非空字符串 的个数。

关键观察

1. 操作顺序可化简

先执行操作 2 再执行操作 1 的结果，等价于连续执行两次操作 1。
证明：

• 先 2 后 1：$s_1 s_2 s_3 \dots s_n \xrightarrow{\text{op2}} s_1 s_3 s_4 \dots s_n \xrightarrow{\text{op1}} s_3 s_4 \dots s_n$
• 两次 op1：$s_1 s_2 s_3 \dots s_n \xrightarrow{\text{op1}} s_2 s_3 \dots s_n \xrightarrow{\text{op1}} s_3 s_4 \dots s_n$

因此，任意操作序列都可以转化为先执行若干次操作 1，再执行若干次操作 2，而不改变最终得到的字符串集合。
故我们只需考虑形如 $(\text{op1 次数 } i,\ \text{op2 次数 } j)$ 的序列。

2. 操作结果的形式

初始字符串 $s = s_1 s_2 \dots s_n$（下标从 $1$ 开始）。
先做 $i$ 次 op1，剩下 $s_{i+1} s_{i+2} \dots s_n$。
再做 $j$ 次 op2：每次删除当前字符串的 第二个 字符，即依次删除 $s_{i+2}, s_{i+3}, \dots, s_{i+j+1}$。
最终得到的字符串为：

其长度为 $n - i - j$。

3. 何时两个操作对得到相同字符串？

设 $(i_1, j_1)$ 和 $(i_2, j_2)$ 产生相同字符串。

• 长度相等 $\Rightarrow$ $i_1 + j_1 = i_2 + j_2$（总删除次数相同）。
• 第一个字符相等 $\Rightarrow$ $s_{i_1+1} = s_{i_2+1}$。

反之，若满足这两个条件，则两个结果字符串完全相同（因为后续字符都是从同一个位置连续取到末尾）。

4. 压缩状态：只需考虑字符的第一次出现

假设某个字符 $c$ 在位置 $p_1, p_2\ (p_1 < p_2)$ 均出现。
考虑从 $p_2$ 开始（即 $i = p_2-1$）产生的某个字符串：
其第一个字符是 $s_{p_2} = c$，总删除次数为 $i+j = (p_2-1)+j$。

我们可以从 $p_1$ 出发，取 $i' = p_1-1$，并取 $j' = (p_2-1)+j - (p_1-1) = p_2-p_1+j$，则：

• $i'+j' = i+j$（总删除次数相同）
• 第一个字符 $s_{p_1}=c$ 相同

因此从 $p_2$ 得到的所有字符串，都能从更早的首次出现位置 $p_1$ 得到。
结论：每个字符只需考虑它的 第一次出现位置，之后出现的位置不会产生新字符串。

5. 计数方法

对于字符 $c$，设其第一次出现的位置为 $p$（$1$-based）。
固定 $i = p-1$，$j$ 可以取哪些值？
需要保证 $i+j+2 \le n$（因为最后一个保留字符是 $s_n$），即 $j \le n-p-1$。
$j$ 的取值范围是 $0, 1, \dots, n-p-1$，共 $n-p$ 个不同的 $j$。
每个 $j$ 对应一个长度不同的结果字符串，且它们第一个字符相同（都是 $c$），所以互不相同。
因此字符 $c$ 贡献 $\mathbf{n-p}$ 个不同的字符串。

答案 = 对每个首次出现的字符 $c$，累加 $n - \text{pos}(c)$。

最终解法

对于每个测试用例：

• 初始化一个布尔数组 first[26] = false。
• 遍历字符串 $s$，下标 $i$ 从 $0$ 到 $n-1$：
  • 若 first[s[i]-'a'] 为假，则：
    • 答案增加 n - i（因为 $p = i+1$，$n-p+1 = n - (i+1) + 1 = n - i$）。
    • 标记 first[s[i]-'a'] = true。
• 输出答案。

时间复杂度 $O(n)$，空间 $O(1)$。

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        vector<bool> seen(26, false);
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a';
            if (!seen[c]) {
                seen[c] = true;
                ans += n - i;   // n - i = n - (i+1) + 1
            }
        }
        cout << ans << '\n';
    }
    return 0;
}