पायथन में पैलिंड्रॉम बनाने के लिए जोड़े जाने वाले न्यूनतम वर्णों की संख्या ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है। हमें s के बाद जोड़े जाने वाले न्यूनतम वर्णों की संख्या ज्ञात करनी है ताकि यह एक पैलिंड्रॉम बन जाए।

उदाहरण के लिए, s = "mad" के लिए आउटपुट 2 होगा ( "am" जोड़कर "madam" बनाएं)।

एल्गोरिदम (रोलिंग हैश)

• b=256, m=10^9+7
• s := [ord(ch)-97 for ch in s]
• r = l = s[-1], n = len(s), res = n-1, p = b
• i = n-2 से 0 तक:
  • r = (r + s[i]*p) % m
  • l = (l*b + s[i]) % m
  • p = (p*b) % m
  • यदि l == r, तो res = i
• res वापस करें

उदाहरण

class Solution:
    def solve(self, s):
        b = 256
        m = 10**9+7
        s = [ord(ch)-97 for ch 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"

आउटपुट

2