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

মনে করুন আমাদের একটি স্ট্রিং s আছে, আমাদেরそれを প্যালিনড্রোম বানাতে সুসંગত সোয়াপের ন্যূনতম সংখ্যা খুঁজে বের করতে হবে। যদি এটি করার কোনো উপায় না থাকে, তবে -1 রিটার্ন করুন।

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

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

একটি util() ফাংশন সংজ্ঞায়িত করুন। এটি s নিবে।
seen := একটি নতুন ম্যাপ
s এর প্রতিটি i এর জন্য, করুন
- seen[i] := 1 + (seen[i] যদি থাকে অন্যথায় 0)
odd_count := 0
seen এর প্রতিটি কী-মান জোড়ার জন্য, করুন
- যদি মান বিজোড় হয়, তবে
  - odd_count := odd_count + 1
- যদি odd_count 2 এর সমান হয়, তবে
  - False রিটার্ন করুন
True রিটার্ন করুন
মূল মেথড থেকে নিচের কাজগুলো করুন
swaps := 0
যদি util(s) true হয়, তবে
- left := 0
- right := s এর আকার - 1
- s := s থেকে নিয়ে একটি নতুন ক্যারেক্টার তালিকা
- যখন left < right, করুন
  - যদি s[left] s[right] এর সমান না হয়, তবে
    - k := right
    - যখন k > left এবং s[k] s[left] এর সমান না হয়, করুন
      - k := k - 1
    - যদি k left এর সমান হয়, তবে
      - swaps := swaps + 1
      - s[left], s[left + 1] := s[left + 1], s[left]
    - অন্যথায়,
      - যখন k < right, করুন
        s[k], s[k + 1] সোয়াপ করুন
        k := k + 1
        swaps := swaps + 1
      - left := left + 1
      - right := right - 1
  - অন্যথায়,
    - left := left + 1
    - right := right - 1
- swaps রিটার্ন করুন
-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"