STRSRCH - Editorial

PROBLEM LINK:

Practice
Contest

Problem:

Convert string to a palindrome with minimum cost. The operations allowed are :

  1. Swapping characters at any two indices which costs 0 units.
  2. Replacing a character at a particular index to a different character which costs 1 unit.

Editorial:

For each occurrence of character if there exists one more occurrence of the same type then those two can be paired up using 0 or more swapping operations. So if a particular character was there even number of times now it would be paired up entirely and if a particular character was there odd number of times now only one occurrence would be unpaired.

So if X characters are unpaired then we can replace floor(X/2) characters to pair with the other halves. We use floor and not ceil because if there are odd number of characters unpaired then one can be put in the middle of the string and the rest can be paired.

Time Complexity : O(String Size)

C++ Solution