← 返回题目列表

Codeforces · 672/B

B. 不同就是好的

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

一位智者曾经告诉凯雷姆“不同就是好的”,所以凯雷姆希望他生活中的所有事情都不同。

Kerem最近得到了一个由小写英文字母组成的字符串s。由于 Kerem 喜欢事物不同,因此他希望字符串 s 的所有子字符串都是不同的。子字符串是由字符串中一定数量的连续字符组成的字符串。例如,字符串“aba”具有子字符串“”(空子字符串)、“a”、“b”、“a”、“ab”、“ba”、“aba”。

如果字符串 s 至少有两个相等的子字符串,那么 Kerem 会将某些位置的字符更改为其他一些小写英文字母。更改角色是一项非常累人的工作,因此 Kerem 希望执行尽可能少的更改。

你的任务是找到使给定字符串的所有子字符串都不同所需的最少更改次数,或者确定这是不可能的。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) - 字符串 s 的长度。

第二行包含长度为n的字符串s,仅由小写英文字母组成。

输出

如果无法更改字符串 s 使其所有子字符串都不同,则打印 -1。否则打印所需的最少更改次数。

示例

输入 #1

2
aa

输出 #1

1

输入 #2

4
koko

输出 #2

2

输入 #3

5
murat

输出 #3

0

注意

在第一个示例中,可能的解决方案之一是将第一个字符更改为“b”。

在第二个示例中,可以将第一个字符更改为“a”,将第二个字符更改为“b”,因此字符串变为“abko”。