Chương trình Python tìm số cập nhật tối thiểu để chuỗi nửa đơn điệu

Cho chuỗi s chữ thường độ dài chẵn. Cần tìm số ký tự ít nhất phải thay đổi để nửa đầu và nửa sau thỏa mãn một trong 3 điều kiện cho mọi cặp (i, j) với i < n/2, j >= n/2:

1. s[i] > s[j] (nửa đầu > nửa sau)
2. s[i] < s[j] (nửa đầu < nửa sau)
3. s[i] == s[j] (nửa đầu = nửa sau)

Ví dụ

s = "pppxxp" (n=6, nửa đầu="ppp", nửa sau="xxp") → Output: 1

Thay 'p' cuối cùng thành 'x' → "pppxxx" thỏa s[i] < s[j] (p < x).

Thuật toán

1. Đếm tần suất ký tự nửa trái (left) và nửa phải (right).
2. Duyệt mọi ký tự pivot từ 'a' đến 'z':
3. Trường hợp 1 (bằng nhau): đổi tất cả thành pivot → cost = n - left[pivot] - right[pivot].
4. Trường hợp 2 (trái < phải): trái ≤ pivot, phải > pivot → cost = n - good.
5. Trường hợp 3 (trái > phải): trái > pivot, phải ≤ pivot → cost = n - good.
6. Lấy min của tất cả.

Code Python

from collections import Counter
from string import ascii_lowercase

def solve(s):
    n = len(s)
    left = Counter(s[:n//2])
    right = Counter(s[n//2:])
    ans = n
    
    for pivot in ascii_lowercase:
        # Trường hợp 1: tất cả bằng pivot
        ans = min(ans, n - left[pivot] - right[pivot])
        
        # Trường hợp 2: trái <= pivot < phải
        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)
        
        # Trường hợp 3: trái > pivot >= phải
        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

# Test
print(solve("pppxxp"))  # 1
print(solve("aaaaaa"))  # 0 (đã bằng nhau)
print(solve("abcdef"))  # 2

Giải thích ví dụ "pppxxp"

left  = {p:3}
right = {x:2, p:1}
pivot='p':
  equal:     6 - 3 - 1 = 2
  left<=p cost=1  <-- MIN
  left>p>=right: 0 + right[p]=1 = 1 -> cost=5

Độ phức tạp

• Thời gian: O(26 × n) = O(n) (26 là hằng số alphabet).
• Không gian: O(1) (Counter tối đa 26 keys).