สมมติว่าเรามีสตริงตัวพิมพ์เล็กที่มีความยาวเท่ากัน เราต้องหาจำนวนอักขระขั้นต่ำที่ต้องอัปเดตเพื่อให้ตรงกับเงื่อนไขสามข้อต่อไปนี้สำหรับ i ทั้งหมด โดยที่ 0 ≤ i
ดังนั้น หากอินพุตเป็น s ="pppxxp" ผลลัพธ์จะเป็น 1 เพราะหากเราเปลี่ยน "p" สุดท้ายเป็น "x" ก็จะเป็นไปตามเงื่อนไข s[i]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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))
อินพุต
"pppxxp"
ผลลัพธ์
1
