Remove Two Letters

题意翻译

给定一个长度为 $n$ 的字符串，通过删除其中的两个连续字符可以获得 $n-1$ 个新的字符串。求这些新的字符串中有多少个不同的。 本题有多组测试数据。 $1\leq T\leq 10^4,3\leq n\leq 2\times 10^5,\sum n\leq 2\times 10^5$ translated by @[StayAlone](https://www.luogu.com.cn/user/409236)

题目描述

Dmitry has a string $ s $ , consisting of lowercase Latin letters. Dmitry decided to remove two consecutive characters from the string $ s $ and you are wondering how many different strings can be obtained after such an operation. For example, Dmitry has a string "aaabcc". You can get the following different strings: "abcc"(by deleting the first two or second and third characters), "aacc"(by deleting the third and fourth characters),"aaac"(by deleting the fourth and the fifth character) and "aaab" (by deleting the last two).

输入输出格式

输入格式

The first line of input data contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — number of test cases. The descriptions of the test cases follow. The first line of the description of each test case contains an integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ). The second line of the description of each test case contains a string $ s $ of length $ n $ consisting of lowercase Latin letters. It is guaranteed that the sum of $ n $ for all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case print one integer — the number of distinct strings that can be obtained by removing two consecutive letters.

输入输出样例

输入样例 #1

7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa

输出样例 #1

4
1
5
3
3
3
1

说明

The first example is explained in the statement. In the third example, the following strings are obtained: "cdef", "adef", "abef", "abcf", "abcd". In the seventh example, any deletion will result in the string "aba".

题目大意：
给定一个长度为 $n$ 的字符串，通过删除其中的两个连续字符可以获得 $n-1$ 个新的字符串。求这些新的字符串中有多少个不同的。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 $n$（$3 \le n \le 2 \times 10^5$）。
- 第二行包含一个长度为 $n$ 的由小写拉丁字母组成的字符串 $s$。
- 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式：
- 对于每个测试用例，输出一个整数，表示通过删除两个连续字母可以得到的不同字符串的数量。

输入输出样例：
输入样例 #1：
```
7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa
```
输出样例 #1：
```
4
1
5
3
3
3
1
```
题目大意： 给定一个长度为 $n$ 的字符串，通过删除其中的两个连续字符可以获得 $n-1$ 个新的字符串。求这些新的字符串中有多少个不同的。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 $n$（$3 \le n \le 2 \times 10^5$）。 - 第二行包含一个长度为 $n$ 的由小写拉丁字母组成的字符串 $s$。 - 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。 输出格式： - 对于每个测试用例，输出一个整数，表示通过删除两个连续字母可以得到的不同字符串的数量。 输入输出样例： 输入样例 #1： ``` 7 6 aaabcc 10 aaaaaaaaaa 6 abcdef 7 abacaba 6 cccfff 4 abba 5 ababa ``` 输出样例 #1： ``` 4 1 5 3 3 3 1 ```