पायथन में अधिकांश 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
- अगर कश्मीर <=90, तो
  - वापसी 3
- अगर कश्मीर <=98, तो
  - वापसी 2
वापसी 1
फ़ंक्शन f() को परिभाषित करें। इसमें p, k, c, l2 लगेगा
अगर के <0, तो
- 10000 लौटाएं
अगर पी <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