1
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – bluefoggy Oct 24 '14 at 16:16
  • \$\begingroup\$ @kingsdeb: You are welcome. I can update the answer later. \$\endgroup\$ – Martin R Oct 24 '14 at 17:08
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.