โปรแกรมหาคะแนนสูงสุดจากการลบ 10 หรือ 01 ในสตริงไบนารี Python

ได้รับสตริงไบนารี s และคะแนน zero_one (ลบ "01"), one_zero (ลบ "10") ลบ substring ได้ไม่จำกัดครั้ง หา คะแนนสูงสุด

ตัวอย่าง

Input: s = "10100101", zero_one = 3, one_zero = 2

Output: 11

ลบ "01" 3 ครั้ง = 9 แล้วเหลือ "10" ลบได้อีก 2 = 11

แนวทางแก้ปัญหา

Greedy + Stack:

1. ให้คะแนนสูงกว่ามาก่อน: ถ้า zero_one < one_zero → swap คะแนน และ flip ทุกบิต (0↔1)
2. ใช้ stack: วนอ่านบิต
   • ถ้า stack บนสุด < ตัวปัจจุบัน (คือ "01") → pop, ได้คะแนน zero_one
   • มิฉะนั้น push
3. หลังจบ: stack เหลือแค่ 000...111... → จับคู่ 0 กับ 1 ที่เหลือ ได้ min(cnt0, cnt1) × one_zero

การใช้งาน (Python)

class Solution:
    def solve(self, S, zero_one, one_zero):
        A = list(map(int, S))
        
        # ทำให้ zero_one >= one_zero เสมอ
        if zero_one < one_zero:
            zero_one, one_zero = one_zero, zero_one
            A = [x ^ 1 for x in A]  # flip all bits
        
        ans = 0
        stack = []
        
        for x in A:
            if stack and stack[-1] < x:  # 0 then 1 = "01"
                stack.pop()
                ans += zero_one
            else:
                stack.append(x)
        
        # จับคู่ที่เหลือ (เป็น 0...01...1)
        ans += one_zero * min(stack.count(0), stack.count(1))
        return ans

# ทดสอบ
ob = Solution()
print(ob.solve("10100101", 3, 2))  # Output: 11

ความซับซ้อน

• Time Complexity: O(N)
• Space Complexity: O(N)

ข้อสังเกต: หลังลบ "01" ทั้งหมดที่เป็นไปได้ สตริงที่เหลือจะเป็นรูป 000...111... เสมอ