Chương trình đếm số lần hoán vị liền kề nhỏ nhất để thành palindrome trong Python

Cho chuỗi s. Tìm số lần hoán đổi 2 ký tự liền kề tối thiểu để biến thành palindrome. Không thể → -1.

Ví dụ: "xxyy" → 2 (hoán vị giữa → "xyxy", rồi hoán vị đầu → "yxxy").

Giải thuật (Two Pointers + Dịch chuyển ký tự)

1. Kiểm tra khả thi: tối đa 1 ký tự xuất hiện lẻ lần.
2. Two pointers left, right. Nếu s[left] != s[right]:
   • Tìm k từ right về left sao cho s[k] == s[left].
   • Nếu k == left (ký tự lẻ ở giữa): hoán đổi s[left] với s[left+1], swaps++.
   • Ngược lại: dịch chuyển s[k] về vị trí right bằng các hoán vị liền kề, cộng swaps.

Ví dụ minh họa

class Solution:
    def solve(self, s):
        def can_form_palindrome(s):
            from collections import Counter
            cnt = Counter(s)
            odd = sum(1 for v in cnt.values() if v % 2)
            return odd <= 1
        
        if not can_form_palindrome(s):
            return -1
        
        s = list(s)
        swaps = 0
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                k = right
                while k > left and s[k] != s[left]:
                    k -= 1
                if k == left:  # ký tự lẻ, dịch sang phải
                    s[left], s[left + 1] = s[left + 1], s[left]
                    swaps += 1
                else:
                    while k < right:
                        s[k], s[k + 1] = s[k + 1], s[k]
                        swaps += 1
                        k += 1
            left += 1
            right -= 1
        return swaps

ob = Solution()
print(ob.solve("xxyy"))  # Output: 2

Đầu vào / Đầu ra

Input: "xxyy"

Output: 2