โปรแกรมนับคะแนนสูงสุดจากการลบสตริงย่อยใน Python

สมมติว่าเรามีสตริง s และค่าสองค่า x และ y เราสามารถดำเนินการสองประเภทต่อไปนี้ได้ไม่จำกัดจำนวนครั้ง:

• ค้นหาสตริงย่อย "ab" ถ้ามี เราสามารถได้ x คะแนนโดยการลบมัน
• ค้นหาสตริงย่อย "ba" ถ้ามี เราสามารถได้ y คะแนนโดยการลบมัน

เราต้องหาคะแนนสูงสุดที่ได้หลังจากดำเนินการข้างต้นบน s

เช่น ถ้าอินพุตคือ s = "cbbaacdeabb" x = 4 y = 5 ผลลัพธ์จะเป็น 14 เพราะ:

• สตริงเริ่มต้น "cbbaacdeabb" ลบ "ab" ได้ 4 คะแนน เหลือ "cbbaacdeb"
• ลบ "ba" ได้เพิ่ม 5 คะแนน รวม 9 เหลือ "cbacdeb"
• ลบ "ba" อีกครั้ง ได้เพิ่ม 5 คะแนน รวม 14 เหลือ "ccdeb" ไม่มีอะไรลบได้แล้ว

วิธีแก้ปัญหา

• a := 'a', b := 'b'
• ans := 0, a_st := 0, b_st := 0
• ถ้า y > x แล้วสลับ a กับ b และ x กับ y
• สำหรับแต่ละ c ใน s:
  • ถ้า 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 * min(a_st, b_st), a_st := 0, b_st := 0
• return ans + y * min(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

เอาต์พุต

14