পাইথনে একবারের রোটেশনের পর সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোমিক সাবস্ট্রিং খুঁজে বের করার প্রোগ্রাম

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

উদাহরণস্বরূপ, s = "elklev" হলে আউটপুট হবে ৫। ব্যাখ্যা: "el" এবং "klev" এর মাঝপথে রোটেট করলে "levelk" পাওয়া যায়, যার মধ্যে "level" একটি প্যালিনড্রোম যার দৈর্ঘ্য ৫।

সমাধানের পদ্ধতি (ব্রুট-ফোর্স)

1. স্ট্রিং-কে নিজের সাথে দুগুণ করুন: s2 = s + s। এটি সকল সম্ভাব্য রোটেশন ধারণ করে।
2. max_len = 0 ইনিশিয়ালাইজ করুন।
3. x কে ০ থেকে len(s)-1 পর্যন্ত (রোটেশনের শুরু বিন্দু) এবং y কে ০ থেকে len(s) পর্যন্ত (সাবস্ট্রিং-এর দৈর্ঘ্য) লুপ চালান।
4. temp = s2[x : x + y] নিন।
5. যদি temp == temp[::-1] (প্যালিনড্রোম) এবং len(temp) > max_len হয়, তবে max_len আপডেট করুন।
6. শেষে max_len রিটার্ন করুন।

দ্রষ্টব্য: এই পদ্ধতির টাইম কমপ্লেক্সিটি O(n³) যা বড় ইনপুটের জন্য অপ্টিমাইজড নয়। ম্যানachers অ্যালগরিদম বা এক্সপ্যান্ড-অরাউন্ড-সেন্টার দিয়ে O(n²)-এ করা যায়।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, s):
        s2 = 2 * s
        max_len = 0
        for x in range(len(s)):
            for y in range(len(s) + 1):
                temp = s2[x : x + y]
                if temp == temp[::-1] and len(temp) > max_len:
                    max_len = len(temp)
        return max_len

ob = Solution()
s = "elklev"
print(ob.solve(s))

ইনপুট

"elklev"

আউটপুট

5