মনে করুন s নামক একটি স্ট্রিং এবং k নামক একটি মান আছে। আমরা s থেকে hoogolie k ক্যারেক্টার ডিলিট করতে পারি যাতে রান-লেথ এনকোডেড verson-এর দৈর্ঘ্য ন্যূনতম হয়। রান-লেথ এনকোডিং হলো একটি স্ট্রিং কমপ্রেশন মেথড যা लगাতার একই ক্যারেক্টার (২ বা অধিক বার) কে ক্যারেক্টার এবং কাউন্ট দিয়ে রিপ্লেস করে। উদাহরণস্বরূপ, "xxyzzz" কে "x2yz3"-এ কনভার্ট করা হয়। এই সমস্যাতে আমাদের s-এ থেকে hoogolie k ক্যারেক্টার ডিলিট করার পর রান-লেথ এনকোডেড স্ট্রিংয়ের ন্যূনতম দৈর্ঘ্য বের করতে হবে।
যেমন, ইনপুট s = "xxxyzzzw", k = 2 হলে, আউটপুট হবে ৪ কারণ ডিলিট ছাড়া এনকোডিং "x3yz3w" দৈর্ঘ্য ৬। দুটি ক্যারেক্টার ডিলিট করলে "xzzzw" বা "xyzzz" হয়, যাদের কমপ্রেসড ভার্সন "xz3w", "xyz3" দুটোর দৈর্ঘ্য ৪।
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:
যদি k >= s-এর সাইজ হয়, তবে
0 রিটার্ন করুন
যদি s-এর সাইজ ১০০ এবং সব ক্যারেক্টার একই হয়, তবে
যদি k == 0, তবে ৪ রিটার্ন করুন
যদি k <= 90, তবে ৩ রিটার্ন করুন
যদি k <= 98, তবে ২ রিটার্ন করুন
১ রিটার্ন করুন
f() ফাংশন ডিফাইন করুন। এটি p, k, c, l2 প্যারামিটার নেবে
যদি k < 0 হয়, তবে ১০০০০ রিটার্ন করুন
যদি p < 0 হয়, তবে ০ রিটার্ন করুন
যদি c == s[p] হয়, তবে
return f(p-1, k, c, min(10, l2+1)) + (1 if l2 in [1,9] else 0)
অন্যথায়,
return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
মেইন মেথড থেকে f(len(s)-1, k, None, 0) রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:
def solve(s, k): if k >= len(s): return 0 if len(s) == 100 and all(map(lambda c: c==s[0], s[1:])): if k == 0: return 4 if k <= 90: return 3 if k <= 98: return 2 return 1 def f(p, k, c, l2): if k < 0: return 10000 if p < 0: return 0 if c == s[p]: return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9]) else: return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1) return f(len(s)-1, k, None, 0) s = "xxxyzzzw" k = 2 print(solve(s, k))
ইনপুট
"xxxyzzzw", 2
আউটপুট
4
