ধরুন আমাদের কাছে ছোট এবং বড় হাতের ইংরেজি অক্ষর সহ একটি স্ট্রিং রয়েছে। আমরা বিবেচনা করব একটি স্ট্রিং একটি ভাল স্ট্রিং যার কোনো দুটি সন্নিহিত অক্ষর s[i] এবং s[i + 1] নেই যেখানে −
-
0 <=i <=s - 2
এর আকার -
s[i] ছোট হাতের অক্ষর এবং s[i + 1] একই অক্ষর কিন্তু বড় হাতের বা তার বিপরীতে।
একটি স্ট্রিংকে ভালো স্ট্রিংয়ে রূপান্তর করতে, আমরা দুটি সংলগ্ন অক্ষর নির্বাচন করতে পারি যা স্ট্রিংটিকে খারাপ করে এবং সেগুলিকে সরিয়ে দেয়। স্ট্রিং ভাল না হওয়া পর্যন্ত আমরা এই প্রক্রিয়াটি চালিয়ে যাব, (একটি খালি স্ট্রিং একটি ভাল হতে পারে)। স্ট্রিংটি ভালো করার পর আমাদের খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি s ="popPpulaBbr" এর মত হয়, তাহলে আউটপুট হবে "জনপ্রিয়", কারণ প্রথমে হয় "p P মুছে ফেলুন। " বা "Pp " এবং "Bb" মুছুন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
res :=একটি নতুন তালিকা
-
প্রতিটি অক্ষরের জন্য s-এ ch, do
-
যদি res খালি না হয় এবং res-এর শেষ উপাদানটি উপরের বা নিচের যেকোন ক্ষেত্রে ch এর মতই হয়, তাহলে
-
res
থেকে শেষ উপাদান মুছুন
-
-
অন্যথায়,
-
res এর শেষে ch ঢোকান
-
-
-
res এ উপস্থিত প্রতিটি উপাদান যোগ করুন এবং এটি ফেরত দিন
উদাহরণ (পাইথন)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(s): res = [] for ch in s: if res and res[-1] != ch and res[-1].lower() == ch.lower(): res.pop() else: res.append(ch) return ''.join(res) s = "popPpulaBbr" print(solve(s))
ইনপুট
"popPpulaBbr"
আউটপুট
popular