Chương trình tìm số lần xóa tối thiểu để làm cho chuỗi cân bằng trong Python

Giả sử chúng ta có một chuỗi s chỉ có hai ký tự 's' và 't'. Chúng ta có thể xóa bất kỳ số ký tự nào của s để làm cho chuỗi cân bằng. Chúng ta có thể nói, s là cân bằng khi không có cặp chỉ số (i, j) sao cho i

Vì vậy, nếu đầu vào là s =​​"sststtst", thì đầu ra sẽ là 2 vì chúng ta có thể xóa các ký tự ở chỉ số 2 và 6 ("sststtst" thành "sssttt") hoặc xóa các ký tự ở chỉ số 3 và 6 ("sststtst" thành "sstttt").

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• cum_b:=0

• count_a:=số ký tự trong s

• ans:=infinity

• đối với mỗi x in s, thực hiện

  • nếu x giống với "s" thì

    • count_a:=count_a - 1

    • ans:=tối thiểu ans và (cum_b + count_a)

  • nếu không,

    • cum_b:=cum_b + 1

    • ans:=tối thiểu ans và (cum_b-1 + count_a)

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"sststtst"

Đầu ra

2