โปรแกรมนับจำนวนการสปขั้นต่ำเพื่อทำให้เป็นพาลินโดรมใน Python

ได้รับสตริง s หา จำนวน adjacent swaps น้อยที่สุด เพื่อทำให้เป็นพาลินโดรม ไม่ได้ → -1

ตัวอย่าง

Input: "xxyy"

Output: 2

Swap กลาง: xxyy → xyxy → xyxy → yxxy (พาลินโดรม)

แนวทางแก้ปัญหา

1. ตรวจสอบก่อนว่าเป็นพาลินโดรมได้ไหม: นับความถี่ ตัวอักษรที่มีคี่ได้สูงสุด 1 ตัว
2. Two pointers left, right หน้าหลัง:
   • ถ้า s[left] == s[right] → left++, right--
   • ถ้าไม่ตรง → หาตัวตรงกับ s[left] จากขวาไปซ้าย (k)
     • ถ้าหาไม่เจอ (k == left) → นี่คือตัวกลาง (odd char) → swap กับตัวถัดไป left+1, swaps++
     • ถ้าเจอ → bubble สลับมาที่ right นับ swaps

การใช้งาน (Python)

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:
                    # ตัวกลาง - swap เข้าไปทีละนิด
                    s[left], s[left + 1] = s[left + 1], s[left]
                    swaps += 1
                else:
                    # bubble ไปขวา
                    while k < right:
                        s[k], s[k + 1] = s[k + 1], s[k]
                        swaps += 1
                        k += 1
                    left += 1
                    right -= 1
            else:
                left += 1
                right -= 1
        
        return swaps

# ทดสอบ
ob = Solution()
print(ob.solve("xxyy"))  # Output: 2

ความซับซ้อน

• Time Complexity: O(N²)
• Space Complexity: O(N)