পাইথনে স্ট্রিং থেকে ক্যারেক্টার সরিয়ে বা শাফেল করে সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোম বের করা

ধরা যাক একটি স্ট্রিং দেওয়া আছে। আমাদের স্ট্রিং-এর ক্যারেক্টার ডিলিট বা শাফেল করে সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোম বের করতে হবে। যদি একাধিক প্যালিনড্রোম থাকে তবে যেকোনো একটি রিটার্ন করুন।

যেমন, ইনপুট "pqqprrs" হলে আউটপুট "pqrsrqp"।

সমাধানের ধাপসমূহ

count[256] অ্যারে 0 দিয়ে ভরুন
প্রতিটি ক্যারেক্টার এর ফ্রিকোয়েন্সি গণনা করুন
begin, mid, end স্ট্রিং খালি রাখুন
character = 'a' থেকে 'z' পর্যন্ত লুপ:
- যদি count[character] অড্ড হয়: mid = character; count[character]--; character-- (পিছনে যান যেন অন্য অড্ড খুঁজে পান)
- অন্যথায়: count[character]/2 বার begin-এ character যোগ করুন
end = begin রিভার্স
return begin + mid + end

উদাহরণ

def get_palindrome(string):
    count = [0]*256
    for i in range(len(string)):
        count[ord(string[i])] += 1
    begin = ""; mid = ""; end = ""
    character = ord('a')
    while character <= ord('z'):
        if count[character] & 1:
            mid = chr(character)
            count[character] -= 1
            character -= 1
        else:
            for i in range(count[character]//2):
                begin += chr(character)
            character += 1
    end = begin[::-1]
    return begin + mid + end
string = "pqqprrs"
print(get_palindrome(string))

ইনপুট

"pqqprrs"

আউটপুট

pqrsrqp