หา Palindrome ยาวที่สุดจากการลบ/สลับตัวอักษรในสตริง (Python)

โจทย์: กำหนดสตริง หา palindrome ยาวที่สุดที่สร้างได้จากการลบหรือจัดเรียงใหม่ตัวอักษร (คืนค่าใดค่าหนึ่งถ้ามีหลายคำตอบ)

ตัวอย่าง: "pqqprrs" → "pqrsrqp" (ใช้ p:2, q:2, r:2, s:1 → วางคู่ข้างนอก ตัวเดี่ยวกลาง)

อัลกอริทึม

1. นับความถี่ตัวอักษร (count array ขนาด 256)
2. สร้างครึ่งซ้าย (begin): วน a-z นำตัวอักษรแต่ละตัวมา count//2 ตัว
3. ตัวอักษรที่มี count คี่ → วางไว้กลาง (mid) เลือกตัวแรกที่เจอ
4. ครึ่งขวา (end) = reverse ของ begin
5. ผลลัพธ์ = begin + mid + end

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

def get_palindrome(string):
    count = [0] * 256
    for ch in string:
        count[ord(ch)] += 1
    
    begin = ""
    mid = ""
    ch = ord('a')
    while ch <= ord('z'):
        if count[ch] & 1:
            mid = chr(ch)
            count[ch] -= 1
            ch -= 1  # re-check this char
        else:
            for _ in range(count[ch] // 2):
                begin += chr(ch)
        ch += 1
    
    end = begin[::-1]
    return begin + mid + end

print(get_palindrome("pqqprrs"))  # pqrsrqp

ผลลัพธ์

pqrsrqp

สรุป: Greedy: ใช้ตัวอักษรให้มากที่สุด (คู่ๆ ข้างนอก) ตัวคี่วางกลางได้สูงสุด 1 ตัว ให้ palindrome ยาวที่สุดเสมอ