String Compression II

مسئله

با دریافت یک رشته‌ی s (شامل حروف کوچک انگلیسی) و یک عدد صحیح k، شما مجاز هستید حداکثر k کاراکتر از رشته را حذف کنید.

هدف این است که کمترین طول ممکن برای رشته‌ی باقی‌مانده پس از فشرده‌سازی با روش کدگذاری طول اجرا (Run-Length Encoding یا RLE) را برگردانید.

قوانین

1. کدگذاری باید مطابق قوانین مسئله‌ی شماره‌ی ۱۳ انجام شود:

• اگر طول یک دنباله (Run) برابر ۱ باشد، فقط خود کاراکتر نوشته می‌شود.
• اگر طول دنباله بین ۲ تا ۹ باشد، کاراکتر به همراه یک رقم نوشته می‌شود.
• اگر طول دنباله بین ۱۰ تا ۹۹ باشد، کاراکتر به همراه دو رقم نوشته می‌شود.
• این روند برای طول‌های بیشتر نیز ادامه دارد.

تعداد ارقام باید دقیقاً برابر با تعداد ارقام واقعی طول دنباله باشد. برای مثال، عدد 10 با دو رقم نوشته می‌شود، نه با یک رقم ثابت.

2. تعداد حذف‌ها حداکثر k است؛ بنابراین حذف تعداد کاراکترهای کمتر از k نیز مجاز است.

3. خروجی باید طول رشته‌ی فشرده‌شده باشد، نه خود رشته‌ی فشرده‌شده.

4. مرز تغییر تعداد ارقام، مهم‌ترین نکته‌ی این مسئله است.

برای مثال:

• دنباله‌ای با طول ۹، دو کاراکتر هزینه دارد ("a9").
• دنباله‌ای با طول ۱۰، سه کاراکتر هزینه دارد ("a10").

بنابراین ممکن است کوتاه‌تر کردن یک دنباله‌ی طولانی نتیجه‌ی بهتری داشته باشد.

مثال:

اگر رشته‌ی ورودی برابر با "aaaaaaaaaa" و مقدار k برابر با 1 باشد، با حذف یک کاراکتر، رشته به "a9" تبدیل می‌شود و طول آن برابر با ۲ خواهد بود؛ درحالی‌که بدون حذف، "a10" با طول ۳ به دست می‌آید.

محدودیت‌ها

• 1 <= len(s) <= 100
• 0 <= k <= len(s)