পাইথনে সর্বাধিক k অক্ষর মুছে ফেলার পর রান-লেংথ এনকোডিংয়ের সর্বনিম্ন দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s এবং আরেকটি মান k আছে। আমরা s থেকে সর্বাধিক k অক্ষর মুছে ফেলতে পারি যাতে s-এর রান-লেংথ এনকোডেড সংস্করণের দৈর্ঘ্য সর্বনিম্ন হয়। যেমনটি আমরা জানি রান-লেন্থ এনকোডিং হল একটি স্ট্রিং কম্প্রেশন পদ্ধতি যা পরপর অভিন্ন অক্ষরগুলিকে প্রতিস্থাপন করে (2 বা তার বেশি বার) অক্ষরের সংমিশ্রণ এবং অক্ষরগুলির গণনা চিহ্নিত করা সংখ্যার সাথে। উদাহরণস্বরূপ, যদি আমাদের একটি স্ট্রিং "xxyzzz" থাকে তবে আমরা "xx" কে "x2" দ্বারা প্রতিস্থাপন করি এবং "zzz" কে "z3" দ্বারা প্রতিস্থাপন করি। তাই সংকুচিত স্ট্রিং এখন "x2yz3"। তাই এই সমস্যায় আমাদের সর্বাধিক k মান মুছে ফেলার পরে s-এর রান-লেংথ এনকোডেড সংস্করণের সর্বনিম্ন দৈর্ঘ্য খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s ="xxxyzzzw", k =2 এর মত হয়, তাহলে আউটপুট হবে 4 কারণ স্ট্রিং s কিছু মুছে না দিয়ে রান-লেন্থ এনকোডিং হবে "x3yz3w" দৈর্ঘ্য 6। যদি আমরা দুটি অক্ষর সরিয়ে s তৈরি করি। যেমন "xzzzw" বা "xyzzz" তারপর সংকুচিত সংস্করণ হবে "xz3w", "xyz3" উভয়ের দৈর্ঘ্য 4।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

যদি k>=s এর আকার হয়, তাহলে
- রিটার্ন 0
যদি s-এর আকার 100 হয় এবং s-এর সমস্ত অক্ষর একই হয়, তাহলে
- k যদি 0 এর সমান হয়, তাহলে
  - রিটার্ন 4
- যদি k <=90, তাহলে
  - রিটার্ন 3
- যদি k <=98, তাহলে
  - রিটার্ন 2
রিটার্ন 1
একটি ফাংশন সংজ্ঞায়িত করুন f()। এটি p, k, c, l2
লাগবে
যদি k <0, তাহলে
- ফেরত 10000
যদি p <0, তাহলে
- রিটার্ন 0
যদি c s[p] এর মত হয়, তাহলে
- ফেরত দিন f(p-1, k, c, ন্যূনতম 10 এবং l2+1) + 1 যদি l2 হয় 1 বা 9 অন্যথায় 0
অন্যথায়,
- ন্যূনতম f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1
  ফেরত দিন
প্রধান পদ্ধতি থেকে f(s -1, k, null, 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