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)
421import 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}
641function 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}
73Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.