+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک نوار رنگی داریم که به صورت یک سطر افقی شامل $n$ خانه است. هر خانه با یکی از $k$ رنگ موجود رنگ شده است. می‌خواهیم رنگ حداقل تعداد خانه‌ی لازم را تغییر دهیم به صورتی که در نهایت هیچ دو خانه‌ی مجاوری رنگ یکسان نداشته باشند. برای تغییر رنگ خانه‌ها، از هر رنگ دلخواه بین ١ تا $k$ می‌توانیم استفاده کنیم. # ورودی خط اول ورودی شامل دو عدد صحیح $n$ و $k$ است. خط دوم شامل $n$ حرف بزرگ انگلیسی است. حرف `A` به معنای رنگ اول، حرف `B` به معنای رنگ دوم، و به همین ترتیب تا حرف `Z` به معنای رنگ ٢۶ام است. تنها $k$ حرف اول انگلیسی می‌توانند ظاهر شوند. هر حرف نماینده‌ی رنگ خانه متناظرش در نوار است. $$1 \leq n \leq 5 \times 10^5$$ $$2 \leq k \leq 26$$ # خروجی در تنها خط خروجی، حداقل تعداد خانه‌ای که لازم است رنگ آن‌ها عوض شود را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 6 3 ABBACC ``` ## خروجی نمونه ۱ ``` 2 ``` در مثال بالا با تغییر دادن رنگ خانه‌ها از `ABBACC` به `ACBABC` به خواسته ی مورد نظر می‌رسیم. ## ورودی نمونه ۲ ``` 3 2 BBA ``` ## خروجی نمونه ۲ ``` 1 ``` در مثال بالا کافی است رنگ خانه‌ی اول را به `A` تغییر دهیم.

حل سؤال در بانک سؤالات