পাইথনে প্যালিনড্রোম করার জন্য প্রয়োজনীয় ন্যূনতম অদলবদলের সংখ্যা গণনা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের এটিকে প্যালিনড্রোমে পরিণত করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক সংলগ্ন অদলবদল খুঁজে বের করতে হবে। যদি সমাধান করার কোন উপায় না থাকে, তাহলে -1 ফেরত দিন।

সুতরাং, যদি ইনপুটটি s ="xxyy" এর মত হয়, তাহলে আউটপুট হবে 2, যেহেতু আমরা মধ্যম "x" এবং "y" অদলবদল করতে পারি তাই স্ট্রিং "xyxy" এবং তারপর প্রথম দুটি "x" এবং "অদলবদল করতে পারি। y" "yxxy" পেতে, এবং এটি প্যালিনড্রোম।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি s

  লাগবে

• দেখা হয়েছে :=একটি নতুন মানচিত্র

• প্রতিটি i s এর জন্য, do

  • দেখা[i] :=1 + (দেখা হয়েছে[i] যদি থাকে অন্যথায় 0)

• odd_count :=0

• দেখা প্রতিটি কী মান জোড়ার জন্য, করুন

  • যদি মান বিজোড় হয়, তাহলে

    • odd_count :=odd_count + 1

  • যদি odd_count 2 এর সমান হয়, তাহলে

    • রিটার্ন ফলস

• রিটার্ন ট্রু

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• অদলবদল :=0

• যদি util(গুলি) সত্য হয়, তাহলে

  • বাম :=0

  • ডান:=s - 1 এর আকার

  • s :=s

    থেকে নিয়ে অক্ষরের একটি নতুন তালিকা

  • যখন বামে <ডানে, কর

    • যদি s[বাম] s[ডান] এর মত না হয়, তাহলে

      • k :=ডান

      • যখন k> left এবং s[k] s[left] এর মত নয়, do

        • k :=k - 1

      • k যদি বামের মত হয়, তাহলে

        • অদলবদল :=অদলবদল + 1

        • s[left], s[left + 1] :=s[left + 1], s[left]

      • অন্যথায়,

        • যখন k

          • অদলবদল s[k], s[k + 1]

          • k :=k + 1

          • অদলবদল :=অদলবদল + 1

        • left :=left + 1

        • ডান :=ডান - 1

    • অন্যথায়,

      • left :=left + 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