পাইথনে ক্ষতিকারক রান-লেংথ এনকোডিংয়ের ন্যূনতম দৈর্ঘ্য খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি ছোট হাতের স্ট্রিং s এবং আরেকটি মান k আছে। এখন একটি অপারেশন বিবেচনা করুন যেখানে আমরা অ্যাকাউন্ট এবং অক্ষর হিসাবে বারবার ধারাবাহিক অক্ষর রেখে একটি স্ট্রিং-এ একটি রান-দৈর্ঘ্য এনকোডিং করি। সুতরাং স্ট্রিং যদি "aaabbc" এর মতো হয় তবে "3a2bc" হিসাবে এনকোড করা হবে। এখানে আমরা "c" এর জন্য "1c" রাখি না কারণ এটি শুধুমাত্র একবার পরপর প্রদর্শিত হয়। তাই আমরা প্রথমে s-তে যেকোন k-পরপর অক্ষর মুছে ফেলতে পারি, তারপর ফলাফল রান-লেংথেনকোডিংয়ের সম্ভাব্য ন্যূনতম দৈর্ঘ্য খুঁজে বের করতে পারি।

সুতরাং, যদি ইনপুটটি s ="xxxxxyyxxxxxzzxxx", k =2 এর মত হয়, তাহলে আউটপুট হবে 6, কারণ দুটি সুস্পষ্ট পছন্দ হল "yy" বা "zz" s অপসারণ করা। যদি আমরা "yy" s মুছে ফেলি, তাহলে আমরা "10x2z3x" পাব যার দৈর্ঘ্য 7। যদি আমরা "zz" s মুছে ফেলি, তাহলে "5x2y8x" পাব যার দৈর্ঘ্য 6, এটি সবচেয়ে ছোট।

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

• একটি ফাংশন calc_cost() সংজ্ঞায়িত করুন। এটি l

  লাগবে

• যদি l 0 এর সমান হয়, তাহলে

  • রিটার্ন 0

• যদি l 1 এর মত হয়, তাহলে

  • রিটার্ন 1

• অন্যথায়,

  • str(l) + 1

    এর রিটার্ন সাইজ

• একটি ফাংশন উপসর্গ () সংজ্ঞায়িত করুন। এটি s

  লাগবে

  • pre :=একটি তালিকা প্রাথমিকভাবে জোড়া সহ [0, 0]

  • শেষ :=শূন্য

  • প্রতিটি c-এর জন্য s, করুন

    • যদি c শেষের মত হয়, তাহলে

      • একটি জোড়া সন্নিবেশ করান (প্রাকের শেষ আইটেমের 0 তম উপাদান, 1 + পূর্বের শেষ আইটেমের 1 ম উপাদান) প্রি

    • অন্যথায়,

      • সন্নিবেশ করান (প্রি-এর শেষ আইটেমের 0ম উপাদান) + calc_cost(প্রি-এর শেষ আইটেমের প্রথম উপাদান, 1) প্রি

    • শেষ :=c

  • প্রত্যাবর্তন পূর্ব

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:

• pre :=উপসর্গ(গুলি)

• suf :=উপসর্গের বিপরীত (গুলি বিপরীত ক্রমে)

• উত্তর :=অসীম

• i এর জন্য 0 থেকে s - k + 1 এর আকার, do

  • j :=i + k

  • জোড়া (বাম, মধ্য) :=পূর্ব[i]

  • জোড়া (ডান, মধ্য) :=সুফ[জে]

  • খরচ :=বাম + ডান

  • c1 :=s[i - 1] যদি i> 0 অন্যথায় শূন্য

  • c2 :=s[j] যদি j

  • যদি c1 হয় c2 এর মতো, তাহলে

    • খরচ :=খরচ + calc_cost(midl + midr)

  • অন্যথায়,

    • খরচ :=খরচ + calc_cost(midl) + calc_cost(midr)

  • উত্তর :=সর্বনিম্ন উত্তর এবং খরচ

• উত্তর ফেরত দিন

def calc_cost(l):
   if l == 0:
      return 0
   if l == 1:
      return 1
   else:
      return len(str(l)) + 1
class Solution:
   def solve(self, s, k):
      def prefix(s):
         pre = [[0, 0]]
         last = None
         for c in s:
            if c == last:
               pre.append([pre[-1][0], pre[-1][1] + 1])
            else:
               pre.append([pre[-1][0] + calc_cost(pre[-1][1]),1])
            last = c
         return pre
      pre = prefix(s)
      suf = prefix(s[::-1])[::-1]
      ans = float("inf")
      for i in range(len(s) - k + 1):
         j = i + k
         left, midl = pre[i]
         right, midr = suf[j]
         cost = left + right
         c1 = s[i - 1] if i > 0 else None
         c2 = s[j] if j < len(s) else None
         if c1 == c2:
            cost += calc_cost(midl + midr)
         else:
            cost += calc_cost(midl) + calc_cost(midr)
         ans = min(ans, cost)
         return ans
ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2))

s = "xxxxxyyxxxxxzzxxx"

6