একটি স্ট্রিং s দেওয়া থাকলে, এর বাম ও ডান পাশ থেকে কতটুকু ট্রিম (কাট) করে প্যালিনড্রোম বানানো সম্ভব, সেই পদ্ধতির সংখ্যা গণনা করতে হবে।
উদাহরণ: "momo" → আউটপুট 6 (সম্ভাব্য প্যালিনড্রোম: "mom", "omo", "o", "o", "m", "m")।
এক্সপ্যান্ড أرাউন্ড সেন্টার (Expand Around Center) টেকনিক
প্রতিটি ইনডেক্সকে সেন্টার ধরে (অড ও ইভেন দৈর্ঘ্যের জন্য) বাম-ডান এক্সপ্যান্ড করে প্যালিনড্রোম কাউন্ট করা হয়।
পাইথন কোড
def expand(i, j, s):
c = 0
while i >= 0 and j < len(s) and s[i] == s[j]:
i -= 1
j += 1
c += 1
return c
class Solution:
def solve(self, s):
c = 0
for i in range(len(s)):
c += expand(i, i, s) # অড দৈর্ঘ্য (সেন্টার একক ক্যারেক্টার)
c += expand(i, i + 1, s) # ইভেন দৈর্ঘ্য (সেন্টার দুটি ক্যারেক্টার)
return c
ob = Solution()
print(ob.solve("momo")) # 6
টাইম কমপ্লেক্সিটি: O(n²), স্পেস: O(1)। এটি লংগেস্ট প্যালিনড্রোমিক সাবস্ট্রিং সমস্যার ভেরিয়েন্ট।
