- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
هنرمند وسواسی لکه‌ای روی دیوار اتاقش پیدا کرده‌است. این لکه به صورت یک رشته به طول $n$ از حروف کوچک انگلیسی است. هنرمند که خیلی وسواسی است، می‌خواهد هر چه زودتر لکه را پاک کند. او به خاطر وسواس زیادش فقط یکی از دو عملیات زیر را برای پاک کردن انجام می‌دهد:
- یک حرف از این رشته را به یک حرف انگلیسی دیگر تغییر دهد.
- یک زیررشته‌ی متوالی پالیندروم از این رشته را انتخاب کند و آن را حذف کند. منظور از یک رشته‌ی پالیندروم، رشته‌ای است که از هر دو طرف به یک شکل خوانده شود. توجه کنید که با حذف کردن یک زیررشته، دو طرف آن زیررشته به هم می‌چسبند.
برای مثال اگر رشته نمایانگر لکه‌ی aabcx باشد، هنرمند می‌تواند زیررشته‌ی aa را حذف کند چون پالیندروم است و سپس کاراکتر آخر را به b تغییر دهد تا رشته تبدیل به bcb شود. سپس در یک مرحله‌ی دیگر می‌تواند این رشته‌ی پالیندروم را حذف کند.
متاسفانه هنرمند با دیدن لکه بیش از حد وسواسی شده و از شما می‌خواهد با گرفتن رشته‌ی نمایانگر لکه، حداقل تعداد عملیات برای پاک کردن آن را حساب کنید.
ورودی
در تنها خط ورودی رشته‌ی $S$ از حروف کوچک انگلیسی که نمایانگر لکه است، به شما ورودی داده می‌شود.
$$1 \leq |S| \leq 500$$
خروجی
در تنها خط خروجی حداقل تعداد عملیات لازم برای پاک کردن لکه را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
abcba
خروجی نمونه ۱
1
در مثال بالا رشته از همان ابتدا پالیندروم است و در یک مرحله می‌توان آن را پاک کرد.
ورودی نمونه ۲
abcbx
خروجی نمونه ۲
2
در مثال بالا در حرکت اول می‌توان حرف آخر را تبدیل به a کرد و سپس در حرکت دوم رشته‌ی پالیندروم به دست آمده را حذف کرد.
ورودی نمونه ۳
aabcx
خروجی نمونه ۳
3
ارسال پاسخ برای این سؤال