โปรแกรมนับจำนวนการพลิกตัวอักษรให้ x ทั้งหมดอยู่หน้า y ใน Python

คำอธิบายโจทย์

ให้สตริง s ประกอบ x และ y เปลี่ยน x↔y ได้ หาจำนวนการเปลี่ยนน้อยที่สุดเพื่อให้ x ทุกตัวอยู่หน้า y ทุกตัว (รูปแบบ x...xy...y)

ตัวอย่าง

s = "yxyyyyxyxx" → เอาต์พุต: 4

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

Greedy / Prefix Counting:

1. นับ x ทั้งหมด = x_right (จะอยู่ขวาสุด)
2. สแกนซ้ายไปขวา: y_left = จำนวน y ที่ผ่านมา, x_right = จำนวน x ที่เหลืออยู่ขวา
3. ที่แต่ละจุดแบ่ง: ต้องเปลี่ยน y ด้านซ้ายเป็น x (y_left) + x ด้านขวาเป็น y (x_right)
4. หาค่า min ของ y_left + x_right ทุกจุดแบ่ง

โค้ด Python

class Solution:
    def solve(self, s):
        y_left = 0
        x_right = res = s.count("x")
        for item in s:
            if item == "x":
                x_right -= 1
            else:
                y_left += 1
            res = min(res, y_left + x_right)
        return res

ob = Solution()
s = "yxyyyyxyxx"
print(ob.solve(s))

อินพุต

"yxyyyyxyxx"

เอาต์พุต

4