पायथन में उपस्ट्रिंग हटाकर अधिकतम स्कोर गिनने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s और दो मान x और y हैं। हम दी गई दो प्रकार के संचालन किसी भी संख्या में कर सकते हैं।

उपस्ट्रिंग "ab" खोजें, यदि मौजूद है, तो इसे हटाकर x अंक प्राप्त करें।
उपस्ट्रिंग "ba" खोजें, यदि मौजूद है, तो इसे हटाकर y अंक प्राप्त करें।

हमें s पर उपरोक्त संचालन लागू करने के बाद प्राप्त होने वाले अधिकतम अंक ज्ञात करने हैं।

इसलिए, यदि इनपुट है s = "cbbaacdeabb" x = 4 y = 5, तो आउटपुट 14 होगा क्योंकि प्रारंभिक स्ट्रिंग "cbbaacdeabb" है, फिर "cbbaacde(ab)b" हटाकर 4 प्राप्त करें, अब स्ट्रिंग "cbbaacdeb" है, फिर "cb(ba)acdeb" हटाकर 5 और प्राप्त करें, वर्तमान स्कोर 4+5 = 9, अब स्ट्रिंग "cbacdeb" है, फिर फिर से "c(ba)cdeb" हटाकर 5 अतिरिक्त प्राप्त करें, वर्तमान स्कोर 9+5=14, और स्ट्रिंग "ccdeb" है, अब हटाने के लिए कुछ नहीं है।

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

a := 'a', b := 'b'
ans := 0, a_st := 0, b_st := 0
यदि y > x, तो
- a और b को स्वैप करें
- x और y को स्वैप करें
s में प्रत्येक c के लिए, करें
- यदि c a के समान है, तो
  - a_st := a_st + 1
- अन्यथा जब c b के समान है, तो
  - यदि a_st शून्येतर है, तो
    - ans := ans + x
    - a_st := a_st - 1
  - अन्यथा,
    - b_st += 1
- अन्यथा,
  - ans := ans + y * a_st और b_st का न्यूनतम
  - a_st := 0
  - b_st := 0
ans + y * a_st और b_st का न्यूनतम वापस करें

उदाहरण

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

def solve(s, x, y):
    a = 'a'
    b = 'b'
    ans = 0
    a_st = 0
    b_st = 0
    if y > x:
        a, b = b, a
        x, y = y, x
    for c in s:
        if c == a:
            a_st += 1
        elif c == b:
            if a_st:
                ans += x
                a_st -= 1
            else:
                b_st += 1
        else:
            ans += y * min(a_st, b_st)
            a_st = 0
            b_st = 0
    return ans + y * min(a_st, b_st)

s = "cbbaacdeabb"
x = 4
y = 5
print(solve(s, x, y))

इनपुट

"cbbaacdeabb", 4, 5