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
1import java.util.Scanner;
2
3class Solution {
4    public static boolean isValid(String s) {
5        int[] counter = new int[26];
6        int oddCount = 0;
7
8        for (int i = 0; i < s.length(); i++) {
9            counter[s.charAt(i) - 'a']++;
10        }
11        for (int value : counter) {
12            if (value % 2 != 0) {
13                oddCount++;
14            }
15        }
16        return oddCount <= 1;
17    }
18
19    public static int minSwaps(String inp) {
20        if (!isValid(inp)) {
21            return -1;
22        }
23
24        int n = inp.length();
25        char s[] = inp.toCharArray();
26        int count = 0;
27        for (int i = 0; i < n / 2; i++) {
28            int left = i;
29            int right = n - left - 1;
30            while (left < right) {
31                if (s[left] == s[right]) {
32                    break;
33                } else {
34                    right--;
35                }
36            }
37            if (left == right) {
38                // s[left] is the character in the middle of the palindrome
39                char t = s[left];
40                s[left] = s[left + 1];
41                s[left + 1] = t;
42                count++;
43                i--;
44            } else {
45                for (int j = right; j < n - left - 1; j++) {
46                    char t = s[j];
47                    s[j] = s[j + 1];
48                    s[j + 1] = t;
49                    count++;
50                }
51            }
52        }
53        return count;
54    }
55
56    public static void main(String[] args) {
57        Scanner scanner = new Scanner(System.in);
58        String inp = scanner.nextLine();
59        scanner.close();
60        int res = minSwaps(inp);
61        System.out.println(res);
62    }
63}
64
1function isValid(s) {
2    let counter = new Array(26).fill(0);
3    let oddCount = 0;
4
5    for (let i = 0; i < s.length; i++) {
6        counter[s[i].charCodeAt(0) - 97]++;
7    }
8    for (const value of counter) {
9        if (value % 2 != 0) {
10            oddCount++;
11        }
12    }
13    return oddCount <= 1;
14}
15
16function minSwaps(inp) {
17    if (!isValid(inp)) {
18        return -1;
19    }
20
21    const n = inp.length;
22    const s = inp.split('');
23    let count = 0;
24    
25    for (let i = 0; i < Math.floor(n / 2); i++) {
26        const left = i;
27        let right = n - left - 1;
28        while (left < right) {
29            if (s[left] === s[right]) {
30                break;
31            } else {
32                right--;
33            }
34        }
35        if (left === right) {
36            // s[left] is the character in the middle of the palindrome
37            [s[left], s[left + 1]] = [s[left + 1], s[left]];
38            count++;
39            i--;
40        } else {
41            for (let j = right; j < (n - left - 1); j++) {
42                [s[j], s[j + 1]] = [s[j + 1], s[j]]
43                count++;
44            }
45        }
46    }
47    return count;
48}
49
50function* main() {
51    const inp = yield;
52    const res = minSwaps(inp);
53    console.log(res);
54}
55
56class EOFError extends Error {}
57{
58    const gen = main();
59    const next = (line) => gen.next(line).done && process.exit();
60    let buf = '';
61    next();
62    process.stdin.setEncoding('utf8');
63    process.stdin.on('data', (data) => {
64        const lines = (buf + data).split('\n');
65        buf = lines.pop();
66        lines.forEach(next);
67    });
68    process.stdin.on('end', () => {
69        buf && next(buf);
70        gen.throw(new EOFError());
71    });
72}
73