"The Love Letter Mystery" - storing and comparison of strings

Question

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?

Answer 1

(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().

Answer 2

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.