# Advanced Data Structures Algorithms & System Design(HLD+LLD) by Logicmojo

Top tech companies experts provide live online training

Learn Data Structures, Algorithms & System Design

Online live classes from 4 to 7 months programs

Get job assistance after course completion

# Minimum Swaps To Make Palindrome

Back to home
Logicmojo - Updated Aug 28, 2021

## Problem Statement: Minimum Swaps To Make Palindrome

Let's say we have a string s and we need to find the minimum number of adjacent swaps to convert it to a palindrome. Return -1 if there is no method to solve the problem.

A palindrome is a string of letter which is equal to itself when reversed.

Input Format: First line of input contain a string str.
Output Format :Integer value which is the Minimum number of adjacent swaps required to convert the string into palindrome.

Example :
Input: "aabb"
Ouput: 2
Explanation: We can swap the middle "a" and "b" and then swap the first two "a" and "b" to get "baab".

Output: -1
Explanation: we can't make this string as palindrome by swaping the characters.Hence, the output is -1.

### Two Pointer Approach

The steps to solving this problem are outlined below.

1. Consider a two-pointer with the first pointer tracking from the left side of the string and the second pointer tracking from the right side.

2. Continue sliding the right cursor one step left until we discover the same character.

3. Return -1 if the identical character cannot be found.

4. If the same character found then swap the right pointer’s character towards the right until it is not placed at its correct position in a string.

5. Increase left pointer and repeat step 2.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

int countSwap(string s)
{
int n = s.length();

int count = 0;

for (int i = 0; i < n / 2; i++) {
int left = i;

int right = n - left - 1;

while (left < right) {
if (s[left] == s[right]) {
break;
}
else {
right--;
}
}

if (left == right) {
return -1;
}

for (int j = right; j < n - left - 1; j++) {
swap(s[j], s[j + 1]);
count++;
}
}

return count;
}

int main()
{
string s = "aabb";

int ans1 = countSwap(s);
reverse(s.begin(), s.end());
int ans2 = countSwap(s);

cout << max(ans1, ans2);

return 0;
}
```

Java Implementation:

```import java.util.*;
import java.io.*;

class Main {
static int countSwap(String str)
{
int n = str.length();
char[] s = str.toCharArray();
int count = 0;

for (int i = 0; i < n / 2; i++) {
int left = i;
int right = n - left - 1;

while (left < right) {
if (s[left] == s[right]) {
break;
}
else {
right--;
}
}

if (left == right) {
return -1;
}
else {
for (int j = right; j < n - left - 1; j++) {
char t = s[j];
s[j] = s[j + 1];
s[j + 1] = t;
count++;
}
}
}
return count;
}
static void reverse(char a[])
{
int n=a.length;
char[] b = new char[n];
int j = n;
for (int i = 0; i < n; i++) {
b[j - 1] = a[i];
j = j - 1;
}
}

public static void main(String[] args)
{
String s = "aabb";
int ans1 = countSwap(s);

char[] charArray = s.toCharArray();
reverse(charArray);
s = new String(charArray);

int ans2 = countSwap(s);

if (ans1 > ans2)
System.out.println(ans1);
else
System.out.println(ans2);
}
}
```

Python Implementation:

```def CountSwap(s, n):
s = list(s)

count = 0
ans = True
for i in range(n // 2):
left = i

right = n - left - 1

while left < right:
if s[left] == s[right]:
break
else:
right -= 1

if left == right:
ans = False
break
else:
for j in range(right, n - left - 1):
(s[j], s[j + 1]) = (s[j + 1], s[j])
count += 1
if ans:
return (count)
else:
return -1

s = 'aabb'
n = len(s)

ans1 = CountSwap(s, n)
ans2 = CountSwap(s[::-1], n)
print(max(ans1, ans2))
```

Time complexity: Since we are running two nested loops on the length of string, the time complexity is O(n^2)

Space complexity: Since we aren’t using any extra space, Therefore Auxiliary space used is O(1).

With this article at Logicmojo, you must have the complete idea of solving Minimum Swaps To Make Palindrome problem.