Keyboard Purchase
Contest: Educational Codeforces Round 74 (Rated for Div. 2)
Difficulty rating: 2200
Tags: bitmasks, dp

You have a password which you often type — a string $$$s$$$ of length $$$n$$$. Every character of this string is one of the first $$$m$$$ lowercase Latin letters.

Since you spend a lot of time typing it, you want to buy a new keyboard.

A keyboard is a permutation of the first $$$m$$$ Latin letters. For example, if $$$m = 3$$$, then there are six possible keyboards: abc, acb, bac, bca, cab and cba.

Since you type your password with one finger, you need to spend time moving your finger from one password character to the next. The time to move from character $$$s_i$$$ to character $$$s_{i+1}$$$ is equal to the distance between these characters on keyboard. The total time you have to spend typing the password with a keyboard is called the slowness of this keyboard.

More formaly, the slowness of keyboard is equal to $$$\sum\limits_{i=2}^{n} |pos_{s_{i-1}} - pos_{s_i} |$$$, where $$$pos_x$$$ is position of letter $$$x$$$ in keyboard.

For example, if $$$s$$$ is aacabc and the keyboard is bac, then the total time of typing this password is $$$|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$$$.

Before buying a new keyboard you want to know the minimum possible slowness that the keyboard can have.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5, 1 \le m \le 20$$$).

The second line contains the string $$$s$$$ consisting of $$$n$$$ characters. Each character is one of the first $$$m$$$ Latin letters (lowercase).

Output format:
Print one integer – the minimum slowness a keyboard can have.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first test case is considered in the statement.

In the second test case the slowness of any keyboard is $$$0$$$.

In the third test case one of the most suitable keyboards is bacd.

Example input:
6 3
aacabc

Example output:
5

Example input:
6 4
aaaaaa

Example output:
0

Editorial:
Let's solve this problem by subset dynamic programming.
Let's denote $$$cnt_{x, y}$$$ as the number of adjacent characters ($$$s_i$$$ and $$$s_{i+1}$$$) in $$$s$$$ such that $$$s_i = x, s_{i+1} = y$$$ or $$$s_i = y, s_{i+1} = x$$$.
Let's $$$dp_{msk}$$$ be some intermediate result (further it will be explained what kind of intermediate result) if we already added letters corresponding to subset $$$msk$$$ to the keyboard (and we don't care about the order of these letters).
Now let's consider how to recalculate values of this dynamic programming using some $$$dp_{msk}$$$. Let's iterate over a new letter $$$x$$$ on keyboard (and we know the position of this letter on the keyboard: it's equal to the number of elements in $$$msk$$$). After adding this new letter, we want to calculate what it added to the $$$dp_{msk \cup x}$$$. Let consider some letter $$$y \neq x$$$ and calculate how much time will be spent on moving $$$x \rightarrow y$$$ and $$$y \rightarrow x$$$. There are two cases. If letter $$$y$$$ is already on current keyboard, then we should add to answer $$$cnt_{x, y} (pos_x - pos_y)$$$, and $$$cnt_{x, y} (pos_y - pos_x)$$$ otherwise (where $$$pox_a$$$ is the position of character $$$a$$$ on the keyboard). But we don't know the position of the letter $$$y$$$. Let's fix it as follows. We will add the contribution of some letter when it will be added to the keyboard. So, when we added letter $$$x$$$, we should add the value $$$\sum\limits_{y \in msk} (cnt_{x, y} pos_x) - \sum\limits_{y \notin msk} (cnt_{x, y} pos_x)$$$.
So, the total complexity is $$$O(a^2 2^a + n)$$$.