โปรแกรมหาจำนวนตัวอักษรที่ต้องลบน้อยที่สุดเพื่อให้ A อยู่หน้า B ใน Python

สมมติว่าเรามีสตริง s ประกอบด้วยตัวอักษร A และ B เท่านั้น หาจำนวนตัวอักษรที่ต้องลบน้อยที่สุด เพื่อให้ A ทั้งหมดอยู่ก่อน B ทั้งหมด

ตัวอย่าง

อินพุต: S = "AABAABB"

เอาต์พุต: 1

ลบ A ตัวสุดท้าย ได้ AABBBB (A ทั้งหมดอยู่หน้า B)

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

ใช้การนับแบบ prefix/suffix:

1. a_right = s.count("A") (จำนวน A ทั้งหมด)
2. b_left = 0 (จำนวน B ด้านซ้าย)
3. ans = a_right (กรณีลบ A ทั้งหมด)
4. วนลูปผ่านแต่ละตัวอักษร c ใน s:
   • ถ้า c == "A": a_right -= 1
   • มิฉะนั้น: b_left += 1
   • ans = min(ans, a_right + b_left)
5. คืนค่า ans

การนำไปใช้ใน Python

class Solution:
    def solve(self, s):
        a_right = s.count("A")
        b_left = 0
        ans = a_right
        for i, c in enumerate(s):
            if c == "A":
                a_right -= 1
            else:
                b_left += 1
            ans = min(ans, a_right + b_left)
        return ans

ob = Solution()
S = "AABAABB"
print(ob.solve(S))

อินพุต

"AABAABB"

เอาต์พุต

1