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

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

যদি ইনপুট হয় s = "xxxxxyyxxxxxzzxxx", k = 2, তবে আউটপুট হবে ৬, কারণ "yy" বা "zz" মুছে ফেলা যাচ্ছে। "yy" মুছে ফেললে "10x2z3x" পাওয়া যায় যেটির দৈর্ঘ্য ৭। "zz" মুছে ফেললে "5x2y8x" পাওয়া যায় যেটির দৈর্ঘ্য ৬, এটি ন্যূনতম।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

একটি calc_cost() ফাংশন সংজ্ঞায়িত করুন। এটি l গ্রহণ করবে।
যদি l == 0, ০ ফেরত দিন।
যদি l == 1, ১ ফেরত দিন।
অন্যথায়, len(str(l)) + 1 ফেরত দিন।
একটি prefix() ফাংশন সংজ্ঞায়িত করুন। এটি s গ্রহণ করবে।
pre := [[0, 0]] তালিকা, last := None
s-এ থাকা প্রতিটি c-এর জন্য: যদি c == last, pre-এ [pre[-1][0], pre[-1][1]+1] যোগ করুন, অন্যথায় pre-এ [pre[-1][0] + calc_cost(pre[-1][1]), 1] যোগ করুন। last := c। pre ফেরত দিন।
মূল মেথড থেকে: pre := prefix(s), suf := prefix(s[::-1])[::-1], ans := infinity। i কে ০ থেকে len(s)-k+1 পর্যন্ত লুপ চালান: j := i+k, (left, midl) := pre[i], (right, midr) := suf[j], cost := left + right। c1 := i>0 হলে s[i-1] অন্যথায় None, c2 := j

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

উদাহরণ

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"