Custom keyboard - MarisaOJ: Marisa Online Judge

Rinnosuke wants to type a paragraph

S

$S$ that contains only the first

m

$m$ characters in the alphabet. Marisa wants to build a custom keyboard for him with

m

$m$ keys arranged in a row. The position of each character

c

$c$ in the keyboard is denoted by

p_{c}

$p_c$ , and the tiredness of typing a paragraph

s

$s$ of

n

$n$ characters is given by the formula:

\sum_{i = 1}^{n - 1} | p_{s_{i + 1}} - p_{s_{i}} |

$\sum_{i=1}^{n - 1} |p_{s_{i + 1}} - p_{s_i}|$ Marisa wants to minimize the tiredness for Rinnosuke. Please help her determine the minimum tiredness! ### Input - The first line contains 2 integers

n

$n$ and

m

$m$ . - The second line contains a string

S

$S$ . ### Output - Print the minimum tiredness. ### Constraints -

1 \leq n \leq 10^{5}

$1 \le n \le 10^5$ . -

1 \leq m \leq 20

$1 \le m \le 20$ . ### Example Input:

63 a a c a b c

$6 3 aacabc$

Output:

5

$5$

Note: She arranges the keyboard like this

b a c

$bac$ .

Bitmask DP
	Binary board
	Travelling Salesman Problem 2
	Brewing potion 5
	Subsequences counting
	Wooden house
	Xiangqi
	Packing
	Permutation counting
	Counting tilings
	Superstring
	Custom keyboard
	Mushroom harvesting III

Topic

Dynamic Programming

Bitmasks

Rating

1800

Solution (0)

Solution