Wednesday, 25 June 2014

Number of operations to make it palindrome

 

Introduction

   Recently found an interesting Warmup problems @HackerRank. It’s simple and doesn’t use much algorithms. But has palindrome logic which is my favorite. :). And it came with a scramble love letter on it. Ok!! Here i come.

The Problem

Courtesy: https://www.hackerrank.com/challenges/the-love-letter-mystery

James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words in the letter into palindromes.

While modifying the letters of the word, he follows 2 rules:

(a) He always reduces the value of a letter, e.g. he changes 'd' to 'c', but he does not change 'c' to 'd'.
(b) If he has to repeatedly reduce the value of a letter, he can do it until the letter becomes 'a'. Once a letter has been changed to 'a', it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations he carries out to convert a given string into a palindrome.

Input Format
The first line contains an integer T, i.e., the number of test cases.
The next T lines will contain a string each.

Output Format
A single line containing the number of minimum operations corresponding to each test case.

Constraints
1 ≤ T ≤ 10
1 ≤ length of string ≤ 104
All characters are lower cased english alphabets.

The Solution

 

#include <iostream> #include <cmath> #include <string> using namespace std; int cramble(string str) { int size = str.length(); int count = 0; for(int i = 0, j = size-1; i < j; ++i, --j) { if(str[i] != str[j]) { count += abs(str[i] - str[j]); } } return count; } int main() { int T; cin>>T; for(int i=0; i<T; i++) { string love; cin>>love; cout<<cramble(love)<<endl; } return 0; }
  • The solution is simple enough that the code explains it. We compare the first and last letter in string and try to make it equal. Whatever difference we get is taken into count for how many alterations required.
  • Note that, we move only until the mid of the string. mid of the string is always equal to itself.
  • abs is required since greater letter ASCII code might be in either side, may be on the first or at the last