यह जाँचने के लिए प्रोग्राम कि क्या अजगर में अधिकांश k वर्णों को हटाने के बाद पैलिंड्रोम बनाया जा सकता है या नहीं

मान लीजिए कि हमारे पास एक स्ट्रिंग s है, तो हमें यह जांचना होगा कि ज़्यादा से ज़्यादा k वर्णों को हटाने के बाद हम इस स्ट्रिंग को एक पैलिंड्रोम बना सकते हैं या नहीं।

इसलिए, यदि इनपुट s ="lieuvrel", k =4 जैसा है, तो आउटपुट ट्रू होगा, हम पैलिंड्रोम "स्तर" प्राप्त करने के लिए तीन वर्णों को हटा सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें lcs() । इसमें a, b
. लगेगा
• m :=a का आकार, n :=b का आकार
• तालिका:=आकार का मैट्रिक्स (m + 1) x (n + 1) और 0 से भरें
• 1 से मी की सीमा में i के लिए, करें
  • जे के लिए 1 से n तक, करें
    • यदि a[i - 1], b[j-1] के समान है, तो
      • टेबल[i, j] :=1 + टेबल[i-1, j-1]
    • अन्यथा,
      • तालिका[i, j] :=अधिकतम तालिका[i, j-1] और तालिका[i-1, j]
• रिटर्न टेबल[एम, एन]
• मुख्य विधि से निम्न कार्य करें:
• सही लौटें जब (s का आकार - lcs(s, s का उल्टा) <=k) अन्यथा गलत

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, s, k):
      def lcs(a, b):
         m, n = len(a), len(b)
         table = [[0] * (n + 1) for _ in range(m + 1)]
         for i in range(1, m + 1):
            for j in range(1, n + 1):
               if a[i - 1] == b[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
               else:
                  table[i][j] = max(table[i][j - 1], table[i - 1][j])
         return table[m][n]

      return len(s) - lcs(s, s[::-1]) <= k
     
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))

इनपुट

"lieuvrel", 4

आउटपुट

True