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

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

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

एल्गोरिदम

util(s) फ़ंक्शन परिभाषित करें जो जांचता है कि पैलिंड्रॉम संभव है या नहीं (अधिकतम एक विषम फ्रीक्वेंसी वाला वर्ण)
यदि संभव है:
- swaps := 0, left := 0, right := len(s)-1
- s := list(s)
- जब left < right:
  - यदि s[left] != s[right]:
    - k := right से बाएं खोजें जहां s[k] == s[left]
    - यदि k == left (मिलान नहीं मिला), तो swaps++, s[left], s[left+1] = s[left+1], s[left]
    - अन्यथा, k से right-1 तक स्वैप करें, swaps बढ़ाएं
  - left++, right--
- swaps वापस करें
अन्यथा -1 वापस करें

उदाहरण

class Solution:
    def solve(self, s):
        def util(s):
            seen = {}
            for ch in s: seen[ch] = seen.get(ch, 0) + 1
            odd = sum(1 for v in seen.values() if v & 1)
            return odd <= 1
        swaps = 0
        if util(s):
            left, right = 0, 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
            return swaps
        return -1

ob = Solution()
s = "xxyy"
print(ob.solve(s))

इनपुट

"xxyy"