SP19490 PAUWS - Pair and unpair weightest string
题目描述
有一次我去市场买泰迪熊。店主给我出了一个谜题，并说如果我能给他提供这个问题的正确代码，他会给我想要的东西打很大的折扣。
你会得到一个仅由 'A' 和 'B' 组成，长度为 $N$ 的字符串 $S$。你可以通过改变任意一个字符生成所有可能的字符串。然后，为每个字符串分配权重，找出具有最大权重的字符串，并返回这个最大权重。
分配权重的方法如下：
1. 将 $S[i]$ 与相邻的一个字符（$S[i+1]$ 或 $S[i-1]$）配对。每个字符只能配对一次。配对组合仅限于 'AB' 或 'BA'，其权重为 4。
2. 若 $S[i]$ 保持独立，权重为 1。
3. 每个字符只能选择一次配对或保持独立。
4. 考虑字符的转变：对于每个字符串，统计字符从原字符串 $S[i]$ 改变而来的数量 $K$（$1 \leq i \leq N$）。
5. 对每个可能的字符串，计算总配对和独立字符的权重之和，再减去 $K$，这个结果即为字符串的权重。每个配对只算一次权重。
任务是找出字符串的最大权重。例如，若 $S = "ABB"$，可能的变换有 {"ABB", "ABA", "AAB", "AAA", "BBB", "BBA", "BAB", "BAA"}，对应的权重为 {5, 4, 4, 1, 2, 3, 3, 2}，其中最大权重为 5。
输入格式
第一行是测试用例数量 $t$。对于每个测试用例，第一行包含字符串的长度 $N$。第二行是字符串本身。
输出格式
针对每个测试用例，输出能够获得的最大字符串权重。
说明/提示
$1 \leq N \leq 10^5$，$1 \leq T \leq 500$。
**示例**
**输入**：
```
5
3
ABB
7
ABBBAAA
8
BAAAAAAA
12
AAAAAAAAAAAA
11
ABABBBABABA
```
**输出**：
```
5
12
13
18
21
```
**本翻译由 AI 自动生成**