The Love Letter Mystery [closed]

Question

At Hackerrank.com, the love letter mystery is a simple programming problem, which I already solved.

My solution involved calculating the palindrome and counting the number of operations to do it. On Hackerrank, they have another approach, which I don't understand completely:

Given a string, you have to convert it into a palindrome using a certain set of operations.

Let's assume that the length of the string is L, and the characters are indexed from 0 to L-1. The string will be palindrome, only if the characters at index i and the characters at index (L-1-i) are same. So, we need to ensure that the characters for all such indices are same.

Let's assume that one such set of indices can be denoted by A' and B'. It is given that it takes one operation in decreasing value of a character by 1. So, the total number of operations will be |A'-B'|.We need to calculate this for all such pairs of indices, which can be done in a single for loop. Take a look at the setter's code.

I understand everything up until they mention that the total number of operations are |A'-B'|, the absolute value between the two indices. Why is that? For some reason, my head is being thicker (than usual).

Thanks!

======== EDIT ==========

Hey guys, thanks for your input. I thought that this stackexchange site would had been more appropiate than stackoverflow. Is there any stackexchange site where this question is more appropiate?

Answer 1

The algorithm might make more sense with a sample implementation to look at (here, in Python):

S = raw_input()
L = len(S)
T = 0
for i in range(L/2):
  A = ord(S[i])
  B = ord(S[L-1-i])
  T += abs(A-B)
print T

Let's review the problem description. Each character decrement (e.g. --'b' == 'a') counts as a single operation. The problem is to determine the number of operations required to transform the input string into a palindrome.

The algorithm iterates over half the string, and compares the ordinal value of the character at the current index with that of the character across from it (in its mirrored position). If they are not the same, the one that is larger needs to be decremented, but it doesn't actually need to be checked which is which. Taking the absolute value of the difference will produce the correct number of operations needed regardless.

I think a source of confusion might be the wording, "Let's assume that one such set of indices can be denoted by A' and B'." I believe that the author intended A' and B' to refer to the characters at each of these indices, and not the indices themselves. If they had actually meant to refer to the indices, the algorithm would return the same value for any given string length, which is obviously incorrect.

A golfed version might look like this:

s=map(ord,raw_input())
print sum(abs(s[i]-s[~i])for i in range(len(s)/2))

I suspect Ruby might be a bit shorter, because indexing a string returns the ordinal value, rather than the individual character.