Giả sử chúng ta có một chuỗi chữ thường s có độ dài là chẵn. Chúng ta phải tìm số ký tự tối thiểu cần được cập nhật sao cho một trong ba điều kiện sau được thỏa mãn với mọi i, trong đó 0 ≤ i
Vì vậy, nếu đầu vào là s ="pppxxp", thì đầu ra sẽ là 1 vì nếu chúng ta thay đổi "p" cuối cùng thành "x", thì điều này có thể thỏa mãn điều kiện s [i]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
from collections import Counter
from string import ascii_lowercase
def solve(s):
n = len(s)
left = Counter(s[: n >> 1])
right = Counter(s[n >> 1 :])
ans = n
for pivot in ascii_lowercase:
ans = min(ans, n - left[pivot] - right[pivot])
good = sum(left[c] for c in left if c <= pivot)
good += sum(right[c] for c in right if c > pivot)
ans = min(ans, n - good)
good = sum(left[c] for c in left if c > pivot)
good += sum(right[c] for c in right if c <= pivot)
ans = min(ans, n - good)
return ans
s = "pppxxp"
print(solve(s))
Đầu vào
"pppxxp"
Đầu ra
1
