Longest Chunked Palindrome Decomposition ใน Python: แยกสตริงเป็นพาลินโดรมชิ้นเล็กมากที่สุด

ได้สตริง text ต้องการแบ่งเป็น k ชิ้น (Chunk) มากที่สุด ที่: (1) ทุกชิ้นไม่ว่าง (2) ต่อกันแล้วได้ text (3) ชิ้นที่ i เท่ากับชิ้นที่ k+1-i (Chunk Palindrome)

ตัวอย่าง

"antaprezatepzapreanta" → แบ่งได้ 11 ชิ้น: "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"

ขั้นตอนการแก้ปัญหา (Two Pointers + Greedy)

1. Two Pointers: start=0, end=len-1
2. สร้าง Prefix temp1 จากซ้าย และ Suffix temp2 จากขวา
3. เมื่อ temp1 == temp2: เจอคู่ → Reset temp, ans += 2
4. เลื่อน Pointers: start+=1, end-=1
5. จบลูป: ถ้าความยาวคู่ และเหลือ temp → ans += 1 (กลาง)
6. ถ้าความยาวคี่ → เริ่ม ans=1 (ตัวกลาง)

การติดตั้งใน Python

class Solution:
    def longestDecomposition(self, text):
        start, end = 0, len(text) - 1
        temp1 = temp2 = ""
        ans = 1 if len(text) % 2 else 0
        while start < end:
            temp1 += text[start]
            temp2 = text[end] + temp2
            if temp1 == temp2:
                temp1 = temp2 = ""
                ans += 2
            start += 1
            end -= 1
        if len(text) % 2 == 0 and (temp1 or temp2):
            ans += 1
        return ans

ob = Solution()
print(ob.longestDecomposition("antaprezatepzapreanta"))  # 11

อินพุต / เอาต์พุต

Input: "antaprezatepzapreanta"
Output: 11