Cho hai chuỗi P và Q cùng độ dài chỉ chứa chữ cái thường. Cần đếm số lần tiền xử lý tối thiểu trên P để sau khi áp dụng các phép hoán đổi cho phép thì P = Q.
Các phép hoán đổi cho phép:
- Hoán đổi P[i] và Q[i].
- Hoán đổi P[i] và P[n-i-1].
- Hoán đổi Q[i] và Q[n-i-1].
Một phép tiền xử lý: thay đổi một ký tự trong P thành bất kỳ ký tự nào.
Ví dụ: P = "pqprpqp", Q = "qprpqpp" → kết quả 4.
Giải thuật
Xét từng cặp vị trí đối xứng (i, n-i-1). Với mỗi cặp, đếm tần suất 4 ký tự P[i], P[n-i-1], Q[i], Q[n-i-1]. Dựa trên số ký tự khác nhau (size của map) và sự trùng lặp, tính số lần thay đổi cần thiết:
- size = 4 → cần 2 lần.
- size = 3 → cần 1 + (1 nếu P[i] == P[n-i-1] else 0).
- size = 2 → cần 1 nếu P[i] không xuất hiện 2 lần, ngược lại 0.
Nếu độ dài lẻ, kiểm tra ký tự giữa.
Ví dụ
def count_preprocess(P, Q):
n = len(P)
res = 0
for i in range(n // 2):
my_map = {}
my_map[P[i]] = 1
if P[i] == P[n - i - 1]:
my_map[P[n - i - 1]] += 1
if Q[i] in my_map:
my_map[Q[i]] += 1
else:
my_map[Q[i]] = 1
if Q[n - i - 1] in my_map:
my_map[Q[n - 1 - i]] += 1
else:
my_map[Q[n - 1 - i]] = 1
size = len(my_map)
if size == 4:
res += 2
elif size == 3:
res += 1 + (P[i] == P[n - i - 1])
elif size == 2:
res += my_map[P[i]] != 2
if n % 2 == 1 and P[n // 2] != Q[n // 2]:
res += 1
return res
A = "pqprpqp"
B = "qprpqpp"
print(count_preprocess(A, B))Đầu vào
"pqprpqp", "qprpqpp"
Đầu ra
4