Microsoft Online Assessment (OA) - 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
def min_swaps(inp: str) -> int:
2
-
    # WRITE YOUR BRILLIANT CODE HERE
2
+
  s = list(inp)
3
-
    return 0
3
+
  n = len(inp)
4
4
5
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
+
      else:
20
+
          for j in range(right, n - left - 1):
21
+
              (s[j], s[j + 1]) = (s[j + 1], s[j])
22
+
              count += 1
23
+
  return count
24
+
6
25
if __name__ == '__main__':
7
26
    inp = input()
8
27
    res = min_swaps(inp)
9
28
    print(res)