Last Updated: 26 Aug, 2021

Count Swaps

Moderate

Asked in company

Solve now

Problem statement

A string of letters is called a palindrome if it is equal to itself when reversed. You have given a string ‘STR’. Find the number of adjacent swaps you have to make to convert the string into a palindrome.

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains a string ‘STR’.

Output Format :

For each test case, print a single integer representing the number of swaps required to convert a string into the palindrome or “-1” if it is impossible to convert it into a palindrome.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= |STR| <= 10^3
The string ‘STR’ contains small letters only.   

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The basic idea is first to check whether the count of letters present in the string is even or not. A palindrome can maximum consist of 1 odd count letter. Example: madam, pikkkip. Then we can use a two-pointer approach to check for the first letter and last letter simultaneously. If they match, we move forward or count the number of swaps required to make them equal.

Here is the algorithm :

Store the count of all the letters present in the string.
Check if there is more than one letter with an odd count, return -1.
Create two variables (say, ‘i’ and ‘j’) which will point to the first and last letter, respectively, and initialize them with 0 and ‘N’ - 1 where ‘N’ is the length of the string.
Create a variable (say, ‘COUNT’) that will store the swaps and initialize it with 0.
Run a loop, while ‘i’ is smaller than ‘j’.
- Check if ‘STR[i]’ is equal to ‘STR[j]’
  - Increment ‘i’ with 1 and decrement ‘j’ with 1.
- Else, create a variable (say, ‘TEMP’) and initialize it with ‘j’.
- Run a loop, while ‘STR[i]’ is not equal to ‘STR[TEMP]’
  - Decrement ‘TEMP’ with 1.
- If ‘TEMP’ is equal to ‘i’.
  - Swap ‘STR[TEMP]’ and ‘STR[TEMP + 1]’.
  - Increment ‘COUNT’ with 1.
- Else, run a loop from ‘TEMP’ to ‘j’ (say, iterator ‘k’)
  - Swap ‘STR[k]’ and ‘STR[k + 1]’.
  - Increment ‘COUNT’ with 1.
  - Increment ‘i’ with 1 and decrement ‘j’ with 1.
Finally, return ‘COUNT’.

Solve now