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

1from typing import Counter
2
3def is_valid(s: str) -> bool:
4    count = Counter(s)
5    return len([char for char, freq in count.items() if freq % 2]) <= 1
6
7
8def min_swaps(inp: str) -> int:
9    if not is_valid(inp):
10        return -1
11
12    s = list(inp)
13    n = len(inp)
14
15    count = 0
16    i = 0
17    while i < n // 2:
18        left = i
19        right = n - left - 1
20
21        while left < right:
22            if s[left] == s[right]:
23                break
24            else:
25                right -= 1
26
27        if left == right:
28            # s[left] is the character in the middle of the palindrome
29            (s[left], s[left + 1]) = (s[left + 1], s[left])
30            count += 1
31        else:
32            for j in range(right, n - left - 1):
33                (s[j], s[j + 1]) = (s[j + 1], s[j])
34                count += 1
35            i += 1
36    return count
37
38if __name__ == '__main__':
39    inp = input()
40    res = min_swaps(inp)
41    print(res)
42