পাইথনে লংগেস্ট চাংকড প্যালিনড্রোম ডিকম্পোজিশন (Longest Chunked Palindrome Decomposition)

সমস্যা বিবরণ

একটি টেক্সট দেওয়া থাকে। সেটাকে সর্বোচ্চ k টুকরোতে ভাগ করুন যেন: প্রতিটি টুকরো non-empty, সংযোজনে মূল টেক্সট হয়, এবং i-তম টুকরো = (k+1-i)-তম টুকরো (প্যালিনড্রোমিক কাঙ্ক)।

উদাহরণ

text = "antaprezatepzapreanta" → আউটপুট: 11

ডিকম্পোজিশন: (a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a) — ১১ টুকরো।

এলগরিদম (Two Pointers + Greedy)

1. start=0, end=len-1, temp1="", temp2=""।
2. ans = 1 if len%2 else 0 (মাঝের ক্যারেক্টার için)।
3. while start < end:
   • temp1 += text[start] (বাম থেকে ডানে বিল্ড)।
   • temp2 = text[end] + temp2 (ডান থেকে বামে বিল্ড)।
   • যদি temp1 == temp2 → মিল পেলে ans += 2, temp1=temp2=""।
   • start+=1, end-=1।
4. যদি সম দৈর্ঘ্যের টেক্সটে temp1 বা temp2 বাকি থাকে → ans += 1।
5. ans রিটার্ন।

পাইথন বাস্তবায়ন

class Solution:
    def longestDecomposition(self, text):
        start, end = 0, len(text) - 1
        temp1 = temp2 = ""
        ans = 1 if len(text) & 1 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

ইনপুট / আউটপুট

ইনপুট: "antaprezatepzapreanta"
আউটপুট: 11