Minimum Adjacent Swaps to Make Palindrome

Given a string, what is the minimum number of adjacent swaps required to convert a string into a palindrome. If not possible, return -1.

Example 1:

Input: mamad

Output: 3

Explanation:

swap m with a => maamd

swap m with d => maadm

swap a with d => madam

Example 2:

Input: asflkj

Output: -1

Example 3:

Input: mideld

Output: 3

Explanation:

swap e with l => midled

swap e with d => midlde

swap l with d => middle

Try it yourself

Implementation

1
1
class Solution:
2
2
  def minSwap(self, S: str) -> int:
3
-
    # WRITE YOUR BRILLIANT CODE HERE
3
+
    s = list(S)
4
+
    n = len(S)
5
+
6
+
    count = 0
7
+
    for i in range(n // 2):
8
+
        left = i
9
+
        right = n - left - 1
10
+
11
+
        while left < right:
12
+
            if s[left] == s[right]:
13
+
                break
14
+
            else:
15
+
                right -= 1
16
+
17
+
        if left == right:
18
+
            return -1
19
+
            break
20
+
        else:
21
+
            for j in range(right, n - left - 1):
22
+
                (s[j], s[j + 1]) = (s[j + 1], s[j])
23
+
                count += 1
24
+
    return count
4
25
if __name__ == "__main__":
5
26
    sol = Solution()
6
27
    word1 = input()
7
28
    print(sol.minSwap(word1))