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 collections 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
7def min_swaps(inp: str) -> int:
8 if not is_valid(inp):
9 return -1
10
11 s = list(inp)
12 n = len(inp)
13
14 count = 0
15 i = 0
16 while i < n // 2:
17 left = i
18 right = n - left - 1
19
20 while left < right:
21 if s[left] == s[right]:
22 break
23 else:
24 right -= 1
25
26 if left == right:
27 # s[left] is the character in the middle of the palindrome
28 (s[left], s[left + 1]) = (s[left + 1], s[left])
29 count += 1
30 else:
31 for j in range(right, n - left - 1):
32 (s[j], s[j + 1]) = (s[j + 1], s[j])
33 count += 1
34 i += 1
35 return count
36
37if __name__ == "__main__":
38 inp = input()
39 res = min_swaps(inp)
40 print(res)
411import 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}
641"use strict";
2
3function isValid(s) {
4 const counter = new Array(26).fill(0);
5 let oddCount = 0;
6
7 for (let i = 0; i < s.length; i++) {
8 counter[s[i].charCodeAt(0) - 97]++;
9 }
10 for (const value of counter) {
11 if (value % 2 !== 0) {
12 oddCount++;
13 }
14 }
15 return oddCount <= 1;
16}
17
18function minSwaps(inp) {
19 if (!isValid(inp)) {
20 return -1;
21 }
22
23 const n = inp.length;
24 const s = inp.split("");
25 let count = 0;
26
27 for (let i = 0; i < Math.floor(n / 2); i++) {
28 const left = i;
29 let 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 [s[left], s[left + 1]] = [s[left + 1], s[left]];
40 count++;
41 i--;
42 } else {
43 for (let j = right; j < n - left - 1; j++) {
44 [s[j], s[j + 1]] = [s[j + 1], s[j]];
45 count++;
46 }
47 }
48 }
49 return count;
50}
51
52function* main() {
53 const inp = yield;
54 const res = minSwaps(inp);
55 console.log(res);
56}
57
58class EOFError extends Error {}
59{
60 const gen = main();
61 const next = (line) => gen.next(line).done && process.exit();
62 let buf = "";
63 next();
64 process.stdin.setEncoding("utf8");
65 process.stdin.on("data", (data) => {
66 const lines = (buf + data).split("\n");
67 buf = lines.pop();
68 lines.forEach(next);
69 });
70 process.stdin.on("end", () => {
71 buf && next(buf);
72 gen.throw(new EOFError());
73 });
74}
751function isValid(s: string): boolean {
2 const counter: number[] = new Array(26).fill(0);
3 let oddCount = 0;
4
5 for (let i = 0; i < s.length; i++) {
6 counter[s.charCodeAt(i) - 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: string): number {
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?: string) => 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