Frequency analysis based anagram checker

Question

I uploaded code solutions for some problems of the book Cracking the Coding Interview, 6th Edition to GitHub, I would like to know your rating and potential improvement of the code I wrote.

Here is the first problem of chapter 1 (anagrams):

#include <stdio.h>
#include <string.h>

/*check if one string is an anagram of another, it uses an int array
 * called alphabet to store frequencies of chars in both strings, add
 * 1 for s1 and subtract 1 for s2*/
int are_anagrams(const char *s1, const char *s2) {
    int alphabet[26] = { 0 };
    int index1, index2;
    size_t l1 = strlen(s1), l2 = strlen(s2), i;

    /*if the strings have different lengths are not anagrams */
    if (l1 != l2) return 0;

    /* count the frequencies of characters */
    for (i = 0; i < l1; ++i) {
        index1 = s1[i] - 'a';
        index2 = s2[i] - 'a';
        ++alphabet[index1];
        --alphabet[index2];
    }
    /* all the alphabet letters should be 0, otherwise the strings are not
     * anagrams */
    for (i = 0; i < 26; ++i)
        if (alphabet[i] != 0) return 0;

    return 1;
}

int main() {
    char s1[] = "aaabbbccc";
    char s2[] = "aabbaccbc";
    printf("%d\n", are_anagrams(s1, s2));
    return 0;
}

Any suggestion or advice is welcome, thanks for your time.

Answer 1

• Avoid magic numbers, especially if they, like 26 in your code, are used repeatedly. Along the same line, keep in mind that the code only works in the "C" locale. Other locales may have alphabets of different size.

• Prefer to declare variables as close to use as possible, e.g.

      for (size_t i = 0; i < l1; ++i) {
          int index1 = s1[i] - 'a';
          int index2 = s2[i] - 'a';
          ....
  

• If the string contains non-lowercase characters, the code would do an out-of-bound access. You should ensure islower(s[i]) prior to computing indices, and ask the interviewer about what are the guarantees.

• An opportunistic if (l1 != l2) return 0; is not an optimization. It still require a linear time to compute the lengths.

• Along the same line, length computation is not necessary. An idiomatic C approach is to us pointers:

  while ((ch = *s++) != 0)
  

• The bullets above suggest splitting the loop into two:

  while ((ch = *s1++) != 0) {
      if (islower(ch)) {
          alphabet[ch - 'a']++;
      }
  }
  
  while ((ch = *s2++) != 0) {
      if (islower(ch)) {
          alphabet[ch - 'a']--;
      }
  }
  

• Now, a DRY principle require factoring this loops into a function:

  static void count_frequencies(char * s, int * alphabet, int addend) {
      while ((ch = *s++) != 0) {
          if (islower(ch)) {
              alphabet[ch - 'a'] += addend;
          }
      }
  }
  
  ....
      count_frequencies(s1, alphabet, 1);
      count_frequencies(s2, alphabet, -1);
  

  As a perk benefit, see how the /* count the frequencies of characters */ disappears.

• For a very long string the integer in alphabet may overflow. Could be a nitpick, but could also be a failure, depending on the interviewer.

Answer 2

- <stdbool.h>

Functions that return an int usually return an error code. Unless you need C89 (in 2019!), please, use bool when you want a boolean:

#include <stdbool.h>

bool are_anagrams(const char *s1, const char *s2);

---

- performance

For short strings, which is the expected input in this case, it won't matter, but when dealing with two big arrays, I've found that it is faster to iterate first over one array and then over the other. I guess the reason is in the way the cache and the CPU work.

---

- int main(void)

The only two standard forms of main are:

int main(void)
int main(int argc, char *argv[])

Use one of them.

Answer 3

This part isn't very robust:

    index1 = s1[i] - 'a';
    index2 = s2[i] - 'a';
    ++alphabet[index1];
    --alphabet[index2];

Think of the assumptions we're making here. We're assuming that the input will never contain characters outside the range 'a' to 'a' + 25. Even if the strings do conform to the implicit expectations, there's no guarantee that the execution character set has contiguous positions for the letters (e.g. most ISO 8859 or ECBDIC codings).

A safer approach would be to count all characters, and filter later to just the alphabetic ones. So declare

int alphabet[UCHAR_MAX+1] = { 0 };

Then we can simply:

    ++alphabet[(unsigned char)s1[i]];
    --alphabet[(unsigned char)s2[i]];

Then at the end, count only the alphabetic characters:

for (i = 0;  i < sizeof alphabet;  ++i) {
    if (isalpha(i) && alphabet[i] != 0) {
        return 0;
    }
}

We might want to consider using toupper((unsigned char)s1[i]) when counting, if anagrams are intended to be case-insensitive; that may or may not be specified in the problem statement. Remember, interview questions often test your ability to gather requirements as well as to write code!