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