← 返回题目列表

Codeforces · 1321/C

C. 删除相邻的

中文机器翻译题面 查看原题

给你一个由小写拉丁字母组成的字符串 $$$s$$$。令$$$s$$$ 的长度为$$$|s|$$$。您可以对此字符串执行多种操作。

在一次操作中,您可以选择某个索引 $$$i$$$ 并删除 $$$s$$$ ($$$s_i$$$) 的第 $$$i$$$ 个字符(如果其相邻字符中至少有一个是 $$$s_i$$$ 的拉丁字母表中的前一个字母)。例如,b 的前一个字母是 a,s 的前一个字母是 r,字母 a 没有前一个字母。请注意,每次删除后,字符串的长度都会减少一。因此,索引 $$$i$$$ 在每次操作期间都应满足条件 $$$1 \le i \le |s|$$$。

对于字符 $$$s_i$$$,相邻字符是 $$$s_{i-1}$$$ 和 $$$s_{i+1}$$$。 $$$s$$$ 的第一个和最后一个字符都只有一个相邻字符(除非 $$$|s| = 1$$$)。

考虑以下示例。让$$$s=$$$bacabcab。

1. 在第一次移动过程中,您可以删除第一个字符$$$s_1=$$$ b,因为$$$s_2=$$$ a。那么字符串就变成了$$$s=$$$ acabcab。
2. 在第二次移动过程中,您可以删除第五个字符$$$s_5=$$$ c,因为$$$s_4=$$$ b。那么字符串就变成了$$$s=$$$ acabab。
3. 在第三步中,您可以删除第六个字符$$$s_6=$$$'b',因为$$$s_5=$$$ a。那么字符串就变成了$$$s=$$$ acaba。
4. 在第四步中,您唯一可以删除的字符是 $$$s_4=$$$ b,因为 $$$s_3=$$$ a(或 $$$s_5=$$$ a)。该字符串变成 $$$s=$$$ acaa 并且你不能用它做任何事情。

您的任务是找到在选择最佳操作顺序的情况下可以删除的最大可能数量的字符。

输入

输入的第一行包含一个整数 $$$|s|$$$ ($$$1 \le |s| \le 100$$$) — $$$s$$$ 的长度。

输入的第二行包含一个字符串 $$$s$$$,由 $$$|s|$$$ 小写拉丁字母组成。

输出

打印一个整数 — 如果您选择最佳的移动顺序,则可以删除的最大可能字符数。

示例

输入 #1

8
bacabcab

输出 #1

4

输入 #2

4
bcda

输出 #2

3

输入 #3

6
abbbbb

输出 #3

5

注意

第一个示例在问题陈述中进行了描述。请注意,语句中提供的移动顺序不是唯一的,但可以表明此测试的最大可能答案是 $$$4$$$。

在第二个示例中,您可以删除 $$$s$$$ 中除一个字符外的所有字符。唯一可能的答案如下。

1. 第一次移动时,去掉第三个字符$$$s_3=$$$ d,$$$s$$$ 变成 bca。
2. 第二次移动时,删除第二个字符$$$s_2=$$$ c,$$$s$$$ 变为ba。
3. 在第三步中,删除第一个字符 $$$s_1=$$$ b,$$$s$$$ 变为 a。