← 返回题目列表

Codeforces · 1238/E

E. 键盘购买

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

您有一个经常输入的密码 - 长度为 $$$n$$$ 的字符串 $$$s$$$。该字符串的每个字符都是前 $$$m$$$ 小写拉丁字母之一。

由于您花费大量时间打字,因此您想购买一个新键盘。

键盘是前 $$$m$$$ 拉丁字母的排列。例如,如果 $$$m = 3$$$,则有六种可能的键盘:abc、acb、bac、bca、cab 和 cba。

由于您用一根手指输入密码,因此您需要花时间将手指从一个密码字符移动到下一个密码字符。从字符 $$$s_i$$$ 移动到字符 $$$s_{i+1}$$$ 的时间等于键盘上这些字符之间的距离。您必须用键盘输入密码所花费的总时间称为该键盘的慢度。

更正式地说,键盘的慢度等于 $$$\sum\limits_{i=2}^{n} |pos_{s_{i-1}} - pos_{s_i} |$$$,其中 $$$pos_x$$$ 是字母 $$$x$$$ 在键盘中的位置。

例如,如果$$$s$$$是aacabc,键盘是bac,那么输入该密码的总时间是$$$|pos_a - pos_a| + |pos_a - pos_c| + |pos_c - pos_a| + |pos_a - pos_b| + |pos_b - pos_c|$$$ = $$$|2 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 3|$$$ = $$$0 + 1 + 1 + 1 + 2 = 5$$$。

在购买新键盘之前,您想知道键盘可能出现的最低速度。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5, 1 \le m \le 20$$$)。

第二行包含由 $$$n$$$ 个字符组成的字符串 $$$s$$$。每个字符都是前 $$$m$$$ 拉丁字母(小写)之一。

输出

打印一个整数——键盘可以有的最小速度。

示例

输入 #1

6 3
aacabc

输出 #1

5

输入 #2

6 4
aaaaaa

输出 #2

0

输入 #3

15 4
abacabadabacaba

输出 #3

16

注意

声明中考虑第一个测试用例。

在第二个测试用例中,任何键盘的速度都是 $$$0$$$。

在第三个测试用例中,最合适的键盘之一是 bacd。