পাইথনে স্ট্রিংকে প্যালিনড্রোম বানাতে ন্যূনতম অক্ষর যোগ

একটি স্ট্রিং s দেওয়া আছে। s-এর পরে ন্যূনতম কত অক্ষর যোগ করলে সেটি প্যালিনড্রোম হবে তা বের করতে হবে।

উদাহরণ: s = "mad" হলে আউটপুট ২, কারণ "am" যোগ করলে "madam" হয়।

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

রোলিং হ্যাশ (Rolling Hash) ব্যবহার করুন
b := 256, m := 10^9+7
s কে ASCII-97 তালিকায় রূপান্তর করুন
রিভার্স এবং ফরওয়ার্ড হ্যাশ সমানांतর গণনা করুন
সবচেয়ে বড় প্যালিনড্রোম প্রিফিক্স বের করে ন্যূনতম যোগফল ফেরত দিন

উদাহরণ কোড

class Solution:
    def solve(self, s):
        b = 256
        m = 10 ** 9 + 7
        s = [ord(i) - 97 for i in s]
        r = l = s[-1]
        n = len(s)
        res = n - 1
        p = b
        for i in range(n - 2, -1, -1):
            r = (r + s[i] * p) % m
            l = (l * b + s[i]) % m
            p = (p * b) % m
            if l == r:
                res = i
        return res

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

ইনপুট

"mad"