← 返回题目列表

Codeforces · 701/C

C. 他们无处不在

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

Sergei B.,口袋妖怪的年轻教练,找到了一座大房子,它由从左到右排成一排的 n 个公寓组成。可以从街道进入每间公寓。每个公寓都可以出去。此外,每个单位都与左侧的单位和右侧的单位相连。 1号楼只与2号楼相连,n号楼只与n-1号楼相连。

每间公寓中都有某种类型的神奇宝贝。 Sergei B. 请求房子里的居民允许他进入他们的公寓以便捕捉神奇宝贝。与房子里的居民协商后,决定让 Sergei B. 从街上进入一套公寓,参观几套公寓,然后从其中一套公寓出去。但他们不会让他多次参观同一间公寓。

Sergei B.很高兴,现在他想尽可能少地参观公寓,以便收集出现在这所房子里的所有类型的神奇宝贝。您的任务是帮助他确定他必须访问的最少公寓数量。

输入

第一行包含整数 n (1 ≤ n ≤ 100 000) — 房屋中的公寓数量。

第二行包含长度为n的行s,由英文字母的大小写字母组成,第i个字母等于Pokemon的类型,位于平面数i中。

输出

打印出 Sergei B. 为了捕捉房子里所有类型的神奇宝贝而应该访问的最小公寓数量。

示例

输入 #1

3
AaA

输出 #1

2

输入 #2

7
bcAAcbc

输出 #2

3

输入 #3

6
aaBCCe

输出 #3

5

注意

例如,在第一个测试中,Sergei B. 可以从 1 号公寓开始,到 2 号公寓结束。

在第二个测试中,Sergei B. 可以从 4 号公寓开始,到 6 号公寓结束。

在第三次测试中,Sergei B. 必须从 2 号公寓开始,到 6 号公寓结束。