Count Swaps

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in company
Microsoft

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
mamad
abc
Sample Output 1 :
3
-1
Explanation For Sample Input 1 :
For first test case :

First swap “ad” to make string : mamda
Second swap “md” to make string : madma
Third swap “ma” to make string : madam
Final string : madam which is a palindrome.

For second test :

It is impossible to convert the given string into a palindrome, so the output is “-1”.
Hint

Think of using a two pointer approach to check the first and last elements of a string.

Approaches (1)
Two - pointer 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 :

 

  1. Store the count of all the letters present in the string.
  2. Check if there is more than one letter with an odd count, return -1.
  3. 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.
  4. Create a variable (say, ‘COUNT’) that will store the swaps and initialize it with 0.
  5. 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.
  6. Finally, return ‘COUNT’.
Time Complexity

O(N ^ 2), where ‘N’ is the size of the string.

 

We traverse the letters of the string using the two-pointer approach. If the letters do not match, we use another nested loop to find the matched letter and then swap the letters, which can take a maximum O(N) time. Therefore, the overall time complexity will be O(N ^ 2).

Space Complexity

O(1)

 

We store the count of all letters of the string, which can be a maximum of 26. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Count Swaps
Full screen
Console