पायथन में लॉसी रन-लेंथ एन्कोडिंग की न्यूनतम लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s और एक मान k है। अब एक ऑपरेशन पर विचार करें जहां हम एक स्ट्रिंग पर रन-लेंथ एन्कोडिंग करते हैं जिसमें दोहराए गए क्रमिक वर्णों को एक गिनती और वर्ण के रूप में रखा जाता है। इसलिए यदि स्ट्रिंग "aaabbc" जैसी है तो इसे "3a2bc" के रूप में एन्कोड किया जाएगा। यहां हम "c" के लिए "1c" नहीं डालते क्योंकि यह केवल एक बार क्रमिक रूप से प्रकट होता है। इसलिए हम पहले s में किसी भी k क्रमिक वर्णों को हटा सकते हैं, फिर परिणामी रन-लेंथ एन्कोडिंग की न्यूनतम संभव लंबाई ढूंढ सकते हैं।

इसलिए, यदि इनपुट s = "xxxxxyyxxxxxzzxxx", k = 2 जैसा है, तो आउटपुट 6 होगा, क्योंकि दो स्पष्ट विकल्प "yy" या "zz" को हटाना हैं। यदि हम "yy" हटाते हैं, तो हमें "10x2z3x" मिलेगा जिसकी लंबाई 7 है। यदि हम "zz" हटाते हैं, तो हमें "5x2y8x" मिलेगा जिसकी लंबाई 6 है, यह सबसे छोटा है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

• एक फ़ंक्शन calc_cost() परिभाषित करें। यह l लेगा

• यदि l, 0 के समान है, तो

  • 0 वापस करें

• यदि l, 1 के समान है, तो

  • 1 वापस करें

• अन्यथा,

  • str(l) का आकार + 1 वापस करें

• एक फ़ंक्शन prefix() परिभाषित करें। यह s लेगा

  • pre := प्रारंभ में जोड़ी [0, 0] वाली एक सूची

  • last := null

  • प्रत्येक c के लिए s में, करें

    • यदि c, last के समान है, तो

      • pre के अंतिम आइटम के (0वें तत्व, 1 + 1वें तत्व) की जोड़ी को pre में डालें

    • अन्यथा,

      • pre के अंतिम आइटम के (0वें तत्व) + calc_cost(1वें तत्व, 1) को pre में डालें

    • last := c

  • pre वापस करें

• मुख्य विधि से निम्नलिखित करें:

• pre := prefix(s)

• suf := prefix(s को उल्टे क्रम में) का उल्टा

• ans := infinity

• i के लिए 0 से s के आकार - k + 1 तक की रेंज में, करें

  • j := i + k

  • जोड़ी (left, midl) := pre[i]

  • जोड़ी (right, midr) := suf[j]

  • cost := left + right

  • c1 := s[i - 1] यदि i > 0 अन्यथा null

  • c2 := s[j] यदि j < s का आकार अन्यथा null

  • यदि c1, c2 के समान है, तो

    • cost := cost + calc_cost(midl + midr)

  • अन्यथा,

    • cost := cost + calc_cost(midl) + calc_cost(midr)

  • ans := ans और cost का न्यूनतम

• ans वापस करें

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

उदाहरण

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