โปรแกรมหาจำนวนการอัปเดตน้อยที่สุดเพื่อทำให้สตริงครึ่งหนึ่งเดี่ยวใน Python

คำอธิบายปัญหา

กำหนดสตริงพิมพ์เล็ก s ความยาวคู่ ต้องการหาจำนวนตัวอักษรขั้นต่ำที่ต้องเปลี่ยน ให้เงื่อนไขหนึ่งในสามเป็นจริงสำหรับทุก i (0 ≤ i < n/2) และ j (n/2 ≤ j < n):

1. s[i] > s[j] (ครึ่งซ้ายมากกว่าครึ่งขวาทุกคู่)
2. s[i] < s[j] (ครึ่งซ้ายน้อยกว่าครึ่งขวาทุกคู่)
3. s[i] == s[j] (ครึ่งซ้ายเท่ากับครึ่งขวาทุกคู่)

ตัวอย่าง

s = "pppxxp" → Output: 1 (เปลี่ยน 'p' ตัวสุดท้ายเป็น 'x' ได้ pppxxx ตรงเงื่อนไข s[i] < s[j])

ขั้นตอนการแก้ปัญหา

1. นับความถี่ตัวอักษรในครึ่งซ้าย (left) และครึ่งขวา (right) ด้วย Counter
2. ลองทุกตัวอักษร pivot (a-z) เป็นจุดแบ่ง:
   • กรณีเท่ากัน: ต้องเปลี่ยนทั้งหมดให้เป็น pivot → ต้นทุน = n - left[pivot] - right[pivot]
   • กรณีซ้าย ≤ pivot และ ขวา > pivot: นับจำนวนที่ผ่านเกณฑ์แล้ว (good) ต้นทุน = n - good
   • กรณีซ้าย > pivot และ ขวา ≤ pivot: คำนวณ good เหมือนกัน
3. เลือกค่า ans น้อยที่สุดจากทุก pivot

การตนการทำงาน (Python)

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])
        # กรณีซ้าย <= pivot, ขวา > 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)
        # กรณีซ้าย > pivot, ขวา <= 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)
    return ans

s = "pppxxp"
print(solve(s))  # Output: 1

อินพุต / เอาต์พุต

Input:  "pppxxp"
Output: 1