• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

یک نوار رنگی داریم که به صورت یک سطر افقی شامل nn خانه است. هر خانه با یکی از kk رنگ موجود رنگ شده است. می‌خواهیم رنگ حداقل تعداد خانه‌ی لازم را تغییر دهیم به صورتی که در نهایت هیچ دو خانه‌ی مجاوری رنگ یکسان نداشته باشند. برای تغییر رنگ خانه‌ها، از هر رنگ دلخواه بین ١ تا kk می‌توانیم استفاده کنیم.

ورودی

خط اول ورودی شامل دو عدد صحیح nn و kk است. خط دوم شامل nn حرف بزرگ انگلیسی است. حرف A به معنای رنگ اول، حرف B به معنای رنگ دوم، و به همین ترتیب تا حرف Z به معنای رنگ ٢۶ام است. تنها kk حرف اول انگلیسی می‌توانند ظاهر شوند. هر حرف نماینده‌ی رنگ خانه متناظرش در نوار است.

1n5×1051 \leq n \leq 5 \times 10^5 2k262 \leq k \leq 26

خروجی

در تنها خط خروجی، حداقل تعداد خانه‌ای که لازم است رنگ آن‌ها عوض شود را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

6 3
ABBACC
Plain text

خروجی نمونه ۱

2
Plain text

در مثال بالا با تغییر دادن رنگ خانه‌ها از ABBACC به ACBABC به خواسته ی مورد نظر می‌رسیم.

ورودی نمونه ۲

3 2
BBA
Plain text

خروجی نمونه ۲

1
Plain text

در مثال بالا کافی است رنگ خانه‌ی اول را به A تغییر دهیم.


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.