โปรแกรมค้นหาการลบขั้นต่ำเพื่อให้สตริงสมดุลใน Python

สมมติว่าเรามีสตริง s ที่มีอักขระ 's' และ 't' เพียงสองตัว เราสามารถลบอักขระ s จำนวนเท่าใดก็ได้เพื่อให้สตริงมีความสมดุล เราสามารถพูดได้ว่า s มีความสมดุลเมื่อไม่มีดัชนีคู่ (i,j) ที่ i

ดังนั้น หากอินพุตเป็น s ="sststtst" ผลลัพธ์จะเป็น 2 เพราะเราสามารถลบอักขระที่ดัชนี 2 และ 6 ("sststtst" ถึง "sssttt") หรือลบอักขระที่ดัชนี 3 และ 6 ("sststtst" ถึง "sstttt")

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• cum_b :=0

• count_a :=จำนวนตัวอักษร 's' เป็น s

• ตอบ :=อนันต์

• สำหรับแต่ละ x ใน s ทำ

  • ถ้า x เหมือนกับ "s" แล้ว

    • count_a :=count_a - 1

    • ans :=ขั้นต่ำของ ans และ (cum_b + count_a)

  • มิฉะนั้น

    • cum_b :=cum_b + 1

    • ans :=ขั้นต่ำของ ans และ (cum_b-1 + count_a)

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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