หาจำนวนการเคลื่อนย้ายล่วงหน้าขั้นต่ำเพื่อทำให้สตริงสองตัวเท่ากันใน Python

สมมติว่าเรามีสตริง P และ Q ความยาวเท่ากัน ต้องการหาจำนวนการเปลี่ยนตัวอักษรใน P น้อยที่สุด (การเคลื่อนย้ายล่วงหน้า) เพื่อให้สามารถทำให้ P และ Q เท่ากันได้โดยใช้การดำเนินการ:

• สลับ P[i] กับ Q[i]
• สลับ P[i] กับ P[n-i-1]
• สลับ Q[i] กับ Q[n-i-1]

เช่น P = "pqprpqp", Q = "qprpqpp" ผลลัพธ์คือ 4

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

1. วนลูป i จาก 0 ถึง n//2 - 1
2. สร้างแผนที่นับความถี่ของตัวอักษร 4 ตำแหน่ง: P[i], P[n-i-1], Q[i], Q[n-i-1]
3. นับจำนวนตัวอักษรที่แตกต่างกัน (size):
   • size = 4 → เพิ่ม 2
   • size = 3 → เพิ่ม 1 + (1 ถ้า P[i] == P[n-i-1])
   • size = 2 → เพิ่ม 1 ถ้า P[i] ไม่ปรากฏ 2 ครั้ง
4. ถ้าความยาวคี่ และตัวกลางต่างกัน เพิ่ม 1

ตัวอย่างโค้ด Python

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))

อินพุต

"pqprpqp", "qprpqpp"

เอาต์พุต

4