# “The Love Letter Mystery” - storing and comparison of strings

The problem goes like this.

Change the strings provided by user to form palindromes. To do this, 2 rules are:

(a) Reduce the value of a letter, e.g. Change 'd' to 'c', but cannot change 'c' to 'd'.

(b) In order to form a palindrome, you can repeatedly reduce the value of a letter 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.

This is a HackerRank problem: the-love-letter-mystery

While I was solving it, I made a lot of mistakes. I was using char *str[n] and gets() to input the string. I thought it would work, but I realised after long time that I am not actually allocating any space at all. Later I came up with 2-d array char[n][1000] for storing the strings and scanf seemed to work for me.

Here is my solution:

int main() {

int i, n, len, pos, ops, end;
scanf("%d",&n);
char str[n][10000];
char a,b;
for (i=0;i<n;i++) {
scanf("%s",str[i]);
}
for (i=0;i<n;i++) {
len = strlen(str[i]);
pos = 0;
end = len - 1;
ops = 0;
while ( pos < end) {
a = str[i][pos];
b = str[i][end];
if ( a != b ) {
if ( b > a )
ops = ops + (b -a);
else
ops = ops + (a -b);
}
pos++;
end--;
}
printf("%d\n", ops);
}

return 0;
}


This works perfectly. I also have to assume in the program that the strings can be of max length 1000 as that is one of the constraint.

How can I improve this solution without making it too complex?

(As Yann already said,) There is probably no room to improve your algorithm. But the implementation can be cleaned-up a little.

You don't have to store all input strings in an array. You can read a string, compute the number of operations and print the result, then proceed to the next string. So only one string buffer is needed. The maximal string length should be defined as a constant.

if ( a != b ) {
if ( b > a )
ops = ops + (b -a);
else
ops = ops + (a -b);
}


can be simplified to

ops += abs(a - b);


and then you don't need temporary char variables at all:

ops += abs(str[pos] - str[end]);


I would move the computation part for a single string to a separate function. That makes it easier to add test cases and makes the main function shorter and more clear.

Putting it all together:

static int palindromeOps(const char *str)
{
int pos = 0;
int end = strlen(str) - 1;
int ops = 0;
while (pos < end) {
ops += abs(str[pos] - str[end]);
pos++;
end--;
}
return ops;
}

const int MAXSTRINGLENGTH = 10000;

int main()
{
int n;
char str[MAXSTRINGLENGTH];

scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", str);
int ops = palindromeOps(str);
printf("%d\n", ops);
}

return 0;
}


Remark: Note that generally, reading a string with scanf("%s", str) is not safe and can cause a buffer overflow. This might not be relevant here if we "trust" the input from the programming challenge. As an alternative, you can use something like scanf("%*s", sizeof(str), str) or fgets().

• Thanks for taking out time and answering this. However would like if you could use the fgets only in the code instead of showing with scanf. – bluefoggy Oct 24 '14 at 16:16
• @kingsdeb: You are welcome. I can update the answer later. – Martin R Oct 24 '14 at 17:08

Honestly, this seems pretty good. There might be a faster way to do it, but it's not coming to mind.

I'd maybe not declare your int i that early on, and use the standard format instead, as that's what's expected.

for(int i = 0; i < n; i++)


As well as this, I'd give n a more descriptive name, such as num_lines or something similar. The same can be said for the other variables. ops and pos could give more information about what they're doing.