CF1238E Keyboard Purchase

你有一个经常输入的密码——一个长度为 $n$ 的字符串 $s$。该字符串中的每个字符都是前 $m$ 个小写拉丁字母之一。 由于你经常输入这个密码，你想买一个新键盘。 一个键盘是前 $m$ 个拉丁字母的一个排列。例如，如果 $m=3$，那么可能的键盘有六种：abc、acb、bac、bca、cab 和 cba。 由于你用一根手指输入密码，从一个字符移动到下一个字符需要花费时间。移动时间等于这两个字符在键盘上的距离。用某个键盘输入密码所需的总时间称为该键盘的“慢度”。 更正式地说，键盘的慢度等于 $ \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$ 个小写拉丁字母之一。

输出一个整数，表示键盘可能具有的最小慢度。

第一个测试用例在题目描述中已给出。 第二个测试用例中，任何键盘的慢度都是 $0$。 第三个测试用例中，最合适的键盘之一是 bacd。 由 ChatGPT 4.1 翻译