पायथन में इसे पैलिंड्रोम बनाने के लिए आवश्यक न्यूनतम स्वैप की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक स्ट्रिंग है, हमें इसे पैलिंड्रोम में बनाने के लिए आवश्यक आसन्न स्वैप की न्यूनतम संख्या का पता लगाना होगा। अगर हल करने का ऐसा कोई तरीका नहीं है, तो -1 लौटें।

इसलिए, यदि इनपुट s ="xxyy" जैसा है, तो आउटपुट 2 होगा, क्योंकि हम मध्य "x" और "y" को स्वैप कर सकते हैं, इसलिए स्ट्रिंग "xyxy" है और फिर पहले दो "x" और " y" "yxxy" पाने के लिए, और यह पैलिंड्रोम है।

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

• उपयोग() फ़ंक्शन को परिभाषित करें। इसमें s

  . लगेगा

• देखा :=एक नया नक्शा

• प्रत्येक आई इन एस के लिए, करें

  • देखा [i] :=1 + (देखा [i] अगर मौजूद है तो 0)

• विषम_गणना :=0

• देखे गए प्रत्येक प्रमुख मूल्य युग्म के लिए, करें

  • अगर मान विषम है, तो

    • विषम_गणना :=विषम_गणना + 1

  • अगर विषम_गणना 2 के समान है, तो

    • झूठी वापसी

• सही लौटें

• मुख्य विधि से निम्न कार्य करें -

• स्वैप :=0

• यदि उपयोग सत्य है, तो

  • बायां :=0

  • दाएँ:=s का आकार - 1

  • s :=s से लेकर वर्णों की एक नई सूची

  • जबकि बाएं <दाएं, करें

    • यदि s[बाएं] s[दाएं] के समान नहीं है, तो

      • कश्मीर:=दाएं

      • जबकि k> बाएँ और s[k] s[बाएँ] के समान नहीं हैं, करें

        • कश्मीर:=के - 1

      • यदि k बाएँ जैसा ही है, तो

        • स्वैप :=स्वैप + 1

        • एस [बाएं], एस [बाएं + 1]:=एस [बाएं + 1], एस [बाएं]

      • अन्यथा,

        • जबकि k <दाएं, करें

          • स्वैप s[k], s[k + 1]

          • कश्मीर:=के + 1

          • स्वैप :=स्वैप + 1

        • बाएँ :=बाएँ + 1

        • दाएँ :=दाएँ - 1

    • अन्यथा,

      • बाएँ :=बाएँ + 1

      • दाएँ:=दाएँ - 1

  • वापसी स्वैप

• वापसी -1

उदाहरण (पायथन)

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

class Solution:
   def solve(self, s):
      def util(s):
         seen = {}
         for i in s:
            seen[i] = seen.get(i, 0) + 1
         odd_count = 0
         for k, val in seen.items():
            if val & 1 == 1:
               odd_count += 1
            if odd_count == 2:
               return False
         return True
      swaps = 0
      if util(s):
         left = 0
         right = len(s) - 1
         s = list(s)
         while left < right:
            if s[left] != s[right]:
               k = right
               while k > left and s[k] != s[left]:
                  k -= 1
               if k == left:
                  swaps += 1
                  s[left], s[left + 1] = s[left + 1], s[left]
               else:
                  while k < right:
                     s[k], s[k + 1] = s[k + 1], s[k]
                     k += 1
                     swaps += 1
                  left += 1
                  right -= 1
            else:
               left += 1
               right -= 1
         return swaps
      return -1
ob = Solution()
s = "xxyy"
print(ob.solve(s))

इनपुट

"xxyy"

आउटपुट

2