पायथन में अधिकतम 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