HackerRank: "The Love-Letter Mystery"
Problem Statement
James found a love letter his friend Harry has written for his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter intopalindromes.
To do this, he follows two rules:
He can reduce the value of a letter, e.g. he can change d to c, but he cannot change c to d.
In order to form a palindrome, 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 required 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. The strings do not contain any spaces.
Retrospectively speaking, this problem was a lot of fun. I learned quite a lot! One of the first things I did after reading the problem statement was Googling and refreshing myself on some palindrome algorithms. A popular hit was basically an algorithm to determine if a particular string was a palindrome. This problem was a bit easier because I didn't have to worry about white space, which now thinking about it wouldn't really have given me too much trouble.
The two prime distinctions among the algorithms I found were algorithms that use recursion and algorithms that used loops. Initially, I sought to solve the problem recursively using the following psudocode:
function int palindromize(string)
int numReductions = 0
char firstChar = string[0];
char lastChar = string[length-1]
if (frontChar != backChar)
numReductions += palindromize(string.substring(1, length-1)
return numReductions
However, in the interest of cleaning up code and optimizing the execution time, I decided against using recursion and instead parsed through each String as an array and iterating through the elements using a simple while loop and 2 loop counters, one on either of the string which would increment and decrement towards each other. The pseudocode for this implementation looks something like this:
function int palindromize(string)
char[] charArr = string.toCharArray();
int numReductions = 0;
int frontIndex = 0;
int backIndex = input.length()-1;
while (frontIndex <= backIndex){
char frontChar = inputCharArr[frontIndex];
char backChar = inputCharArr[backIndex];
numReductions += abs(frontChar-backChar);
++frontIndex;
--backIndex;
}
return numReductions;
Here the function "abs()" refers to a function that calculates the absolute value of a value using bitwise operations as follows:
public static int abs(int value){
int mask = value>>31;
return (value ^ mask) - mask;
}
I found this snippet over at StackOverflow in answer #4: http://stackoverflow.com/questions/12041632/how-to-compute-the-integer-absolute-value
Solving the problem this way yielded the best execution times across all test cases.
Here, I learned that simplicity wins out over elegance. I'm much more satisfied with this solution. It's very straight forward and I believe any novice to intermediate programmer can understand the solution without having to think too much.
Source: https://github.com/mbchoa/hackerrank/blob/master/java/algorithms/warmups/mysteryloveletter/LoveLetter.java
