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

Chuỗi s chỉ chứa 's' và 't'. Chuỗi cân bằng khi không có cặp i < j với s[i]='t' và s[j]='s' (tức là mọi 's' đều đứng trước 't'). Tìm số xóa ít nhất để cân bằng.

Ví dụ: s="sststtst" → 2. Xóa chỉ số 2,6 → "sssttt" hoặc xóa 3,6 → "stttt".

Giải thuật (Duyệt 1 lần)

1. cum_b = số 't' đã gặp, count_a = số 's' còn lại.
2. Duyệt từng ký tự x:
   • Nếu x == 's': count_a--, cập nhật ans = min(ans, cum_b + count_a) (xóa tất cả 't' trước + 's' sau).
   • Nếu x == 't': cum_b++, cập nhật ans = min(ans, cum_b-1 + count_a) (giữ 't' này, xóa 't' trước đó + 's' sau).
3. Trả về ans.

Ví dụ minh họ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))

Đầu vào

"sststtst"

Đầu ra

2