Mua bàn phím

Điểm: 8,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Bạn có một mật khẩu là xâu $s$ độ dài $n$ , mỗi ký tự là một trong $m$ chữ cái thường đầu tiên của bảng chữ cái Latin.

Bạn muốn mua một bàn phím mới. Một bàn phím là một hoán vị của $m$ chữ cái đầu tiên — tức là mỗi chữ cái xuất hiện đúng một lần ở một vị trí từ $1$ đến $m$ .

Bạn gõ mật khẩu bằng một ngón tay. Chi phí di chuyển ngón tay từ ký tự $s_{i}$ sang ký tự $s_{i + 1}$ bằng khoảng cách giữa hai vị trí của chúng trên bàn phím. Tổng chi phí gõ toàn bộ mật khẩu được gọi là độ chậm của bàn phím:

$slowness = \sum_{i = 2}^{n} | p o s_{s_{i - 1}} - p o s_{s_{i}} |,$

trong đó $p o s_{x}$ là vị trí của chữ cái $x$ trên bàn phím.

Hãy tìm giá trị nhỏ nhất có thể của độ chậm khi chọn bàn phím thích hợp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ ( $1 \leq n \leq 10^{5}$ , $1 \leq m \leq 20$ ).
Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các chữ cái thường thuộc $m$ chữ cái đầu tiên.

Dữ liệu ra

In ra một số nguyên — độ chậm nhỏ nhất.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq m \leq 20$

Ví dụ

Input	Output	Giải thích
6 3 aacabc	5	Chọn bàn phím bac (vị trí b=1, a=2, c=3): chi phí $‖ 2 - 2 ‖ + ‖ 2 - 3 ‖ + ‖ 3 - 2 ‖ + ‖ 2 - 1 ‖ + ‖ 1 - 3 ‖ = 5$ .
6 4 aaaaaa	0	Mọi ký tự liền kề đều giống nhau nên chi phí luôn bằng 0 với mọi bàn phím.
15 4 abacabadabacaba	16	Một bàn phím tối ưu là bacd.

Bình luận

Không có bình luận tại thời điểm này.