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

ปัญหา

สตริง s มีแค่ 's' และ 't' ลบตัวอักษรได้ ทำให้ไม่มีคู่ (i,j) ที่ i

ตัวอย่าง

s = "sststtst" → ผลลัพธ์ 2 (ลบดัชนี 2,6 ได้ "sssttt" หรือ ลบ 3,6 ได้ "sstttt")

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

1. cum_b := 0, count_a := s.count('s'), ans := inf
2. วน x ใน s:
   • ถ้า x == 's': count_a -= 1; ans = min(ans, cum_b + count_a)
   • มิฉะนั้น: cum_b += 1; ans = min(ans, cum_b - 1 + count_a)
3. คืน ans

การนำไปใช้งาน (Python)

def solve(s):
    cum_b = 0
    count_a = s.count("s")
    ans = float("inf")
    for x in s:
        if x == "s":
            count_a -= 1
            ans = min(ans, cum_b + count_a)
        else:
            cum_b += 1
            ans = min(ans, cum_b - 1 + count_a)
    return ans

s = "sststtst"
print(solve(s))

อินพุต

"sststtst"

เอาต์พุต

2