Confirming existence of lapindromes

Question

The following description is taken from CodeChef.com's Lapindrome problem.

Lapindrome is defined as a string which when split in the middle, gives two halves having the same characters and same frequency of each character. If there are odd number of characters in the string, we ignore the middle character and check for lapindrome. For example gaga is a lapindrome, since the two halves ga and ga have the same characters with same frequency. Also, abccab, rotor and xyzxy are a few examples of lapindromes. Note that abbaab is NOT a lapindrome. The two halves contain the same characters but their frequencies do not match. Your task is simple. Given a string, you need to tell if it is a lapindrome.

Input:

First line of input contains a single integer T, the number of test cases.

Each test is a single line containing a string S composed of only lowercase English alphabet.

Output:

For each test case, output on a separate line: "YES" if the string is a lapindrome and "NO" if it is not.

Constraints:

\$1 ≤ T ≤ 100\$
2 \$≤ |S| ≤ 1000\$, where |S| denotes the length of S.

Example:

Input:

6  
gaga  
abcde  
rotor  
xyzxy  
abbaab  
ababc  

Output:

YES  
NO  
YES  
YES  
NO  
NO  

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        char s[1005];
        scanf("%s",s);
         int len,b[strlen(s)],z;
         int i,j,count =0;
         len=strlen(s);
         for(z=0;z<len;z++)
         {
                b[z] =1;
         }
        if(len%2 !=0)
        {
            for(i=0;i<len/2;i++)
            {
                for(j=(len/2)+1;j<len;j++)
                {
                    if(s[i] == s[j])
                    {
                        if(b[i] && b[j] )
                        {
                            b[i]=0;
                            b[j]=0;
                            count+=1;
                        }
                    }
                }
            }
        }
         else if(len%2 ==0)
        {
            for(i=0;i<len/2;i++)
            {
                for(j=(len/2);j<len;j++)
                {
                    if(s[i] == s[j])
                    {
                        if(b[i] && b[j] )
                        {
                            b[i]=0;
                            b[j]=0;
                            count+=1;
                        }
                    }
                }
            }
        }
        if(count==len/2)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
    }
}

Answer 1

Firstly, there's no reason for us to dump all of this in main.

The logic for determining whether or not a string is a lapindrome can (and should) simply exist in a function that takes a string and returns a bool.

bool isLapindrome(const char *string);

This function has the single responsibility of determining whether or not the input string is a Lapindrome, and it returns a true/false indicating as much.

---

 if(len%2 !=0)
    {
        for(i=0;i<len/2;i++)
        {
            for(j=(len/2)+1;j<len;j++)
            {
                if(s[i] == s[j])
                {
                    if(b[i] && b[j] )
                    {
                        b[i]=0;
                        b[j]=0;
                        count+=1;
                    }
                }
            }
        }
    }
     else if(len%2 ==0)
    {
        for(i=0;i<len/2;i++)
        {
            for(j=(len/2);j<len;j++)
            {
                if(s[i] == s[j])
                {
                    if(b[i] && b[j] )
                    {
                        b[i]=0;
                        b[j]=0;
                        count+=1;
                    }
                }
            }
        }
    }

Correct me if I'm wrong, but by my eyes, the parts inside each half of these if and else are identical except the starting position of the inner loop.

That looks to be the case, so why don't we refactor, starting from the inside and working out.

Rather than nested if statements, we can simply have a single conditional.

if (s[i] == s[j] && b[i] && b[j]) {
    b[i] = 0;
    b[j] = 0;
    ++count;
}

And rather than effectively copy & pasting our loop, we can instead calculate our starting position of the inner loop more effectively:

for (i = 0; i < len/2; ++i) {
    for (j = (len/2 + len%2); j < len; ++j) {

Notice how this produces the same result? Your version of the code is effectively...

if (someCalculation == 1) {
    // ...
        for (j = len/2 + 1; // ...
} else if (someCalculation == 0) {
    // ...
        for (j = len/2 + 0; // ...

(Anything % 2 can only be 1 or 0.)

So we've already eliminated two levels of nesting without even moving anything out to its own function.

for (i = 0; i < len/2; ++i) {
    for (j = (len/2 + len%2); j < len; ++j) {
        if (s[i] == s[j] && b[i] && b[j]) {
            b[i] = 0;
            b[j] = 0;
            ++count;
        }
    }
}

---

Some other comments regarding readability...

All of your variable names are unreadably and meaninglessly short.

• What is s?
• What is b?
• What is i?
• What is j?
• What is z?
• I assume len is length. Why not just use length?

We also have this mess of variable declarations:

int len,b[strlen(s)],z;
int i,j,count =0;
len=strlen(s);

I'm not familiar enough with C to know how expensive strlen is, and while I'm sure it's not horrendous, I also can't imagine it's a completely free call. And when it does make sense to avoid duplicating function calls, we definitely should.

So for starters:

int length = strlen(inputString);

Next, I'd use any one of the options in this Stack Overflow answer to get yourself a bool type for what b is supposed to be.

bool characterChecked[length];

And then, while it is generally okay to use 1-letter variables for loop iterators, I think we should make it more clear what's going on. If you're writing C99 code, you can just declare them straight in the loop:

for(int i = 0; // ...

And this would be ideal, especially when we consider that this limits the variables scope to only within the loop. A variable's scope should be as limited as possible. A variable's scope should be no larger than necessary.

But if you're on C89, this isn't an option. As such, we should declare our variables closer to where the for loop actually exists and potentially even leave a comment.

int i;
for(i = 0; //...

Single letter variable names aren't very self-documenting. (Loop iterators do have some special historical treatment however. But for your other single-letter variables, we definitely need better.)

Answer 2

This can be solved much faster using a different algorithm. The posted code users a quadratic algorithm: comparing every character in the first half of the input with every character in the second half. A linear algorithm is possible:

1. Build an array of character counts for the first half of the input. The size of the array is the size of the alphabet of allowed characters. Initialize it to all zero values. Iterate over the characters of the first half of the input and increment the count for the character.

2. Iterate over the characters of the second half of the input, and decrement the count for the character. If the count drops below zero, you can return false immediately. If you reach the end of the loop, you can return true.

With a single pass over the entire input, this solution will be significantly faster. On the other hand, this algorithm needs extra storage for the array of counts.

In terms of style, please take the suggestions from the other answers. It's a lot easier to spot logical problems in smaller code that's easy to read. Your original code could have been written so much clearer.

As an extra tip, of you want to print simple text without variables ending with a newline, it's more efficient to use puts instead of printf. And you could further simplify the last if-else condition with a ternary:

puts(count == len / 2 ? "YES" : "NO");

Answer 3

1. Why don't you treat the array b as a string instead of a hash table, which could cost you a larger amount of memory?

   memset(b,0,128*sizeof(int));
   
   
   for(z=0;z<len/2;z++)
   count+=!!(++b[s[z]]);
   

2. Don't use nested loops where unnecessary.

3. Proceed to reverse operation from len/2+1:

   for(z=len/2+len%2;z<len;z++)
   {
   count-=!!b[s[z]]--;
   if ((b[s[z]])<0)
      break;
   }
   

4. Last check:

   printf("%s\n",!count?"yes":"no");
   

Here is a solution that could account for both memory and time.