โปรแกรมหาสตริงสั้นที่สุดหลังลบบิตติดกันที่ต่างกันใน Python

สมมติว่าเรามีสตริงไบนารี s เราสามารถลบตัวอักษรสองตัวที่อยู่ติดกันได้หากพวกมันต่างกัน สุดท้ายเราต้องหาความยาวของสตริงที่เล็กที่สุดที่เราสามารถได้ หากเราทำการดำเนินการนี้ได้จำนวนครั้งเท่าก็ตาม

ตัวอย่าง

หากอินพุตคือ s = "1100011" ผลลัพธ์จะเป็น 1 เนื่องจากหลังลบ "10" จะได้ "10011" แล้วลบ "10" อีกครั้งได้ "011" แล้วลบ "01" จะเหลือ 1

ขั้นตอนการแก้ปัญหา

1. stack := รายการใหม่
2. สำหรับแต่ละ c ใน s:
   • ถ้า stack ว่าง หรือค่าบนสุดของ stack เท่ากับ c ให้เพิ่ม c เข้า stack
   • อื่นๆ (ค่าบนสุดไม่เท่ากับ c) ให้ลบค่าบนสุดออกจาก stack
3. คืนค่าจำนวนองค์ประกอบใน stack

การใช้งาน

class Solution:
    def solve(self, s):
        stack = []
        for c in s:
            if not stack or stack[-1] == c:
                stack.append(c)
            elif stack[-1] != c:
                stack.pop()
        return len(stack)

ob = Solution()
print(ob.solve("1100011"))

อินพุต

"1100011"

เอาต์พุต

1