Finding the most frequent character in a string

Question

This is in C/C++ (using a c-string as input). I'm curious if my solution could be more efficient than it currently is.

char mostFrequent(char *bytes, int length) {
  char holder[26];
  for (int i = 0; i < 26; i++) {
    holder[i] = 0;
  }

  for (int i = 0; i < length; i++) {
    holder[bytes[i]-97] += 1;
  }

  char b = 97; // a
  int count = holder[0];
  for (int i = 1; i < 26; i++) {
    if (holder[i] > count) {
      count = holder[i];
      b = i+97;
    }
  }

  return b;
}

Answer 1

If you are intended to measure the frequency of bytes, as the name of your input string seems to suggest, rather than just lowercase ASCII letters, then your holder array should be 256 elements long.

This also saves you from all the additions and subtractions of the 'magic' number 97. (Seriously, you could have used 'a'.)

Also, your holder array should consist of ints not chars, because if a certain byte appears more than 256 times in your input string the char will wrap around to zero. Also an array of ints will probably perform more efficiently due to memory alignment.

Answer 2

Apart from everything that's been said already, you could improve the code by making it more const-correct. This may be different for C, but in C++, you almost certainly want to have

char mostFrequent(char const* bytes, int length) {

This will allow your function to be called with string literals without invoking a deprecated conversion (char const* to char*).

In addition to this, if you know you're going to be working with strings, you might as well have it use null-termination, as you can expect it to be present anyway. It also allows for more elegant (in my opinion) expression of the intent, especially if you use 'a' instead of 97.

char mostFrequent(char const* bytes) {
    // Leaving this array as it is to change the rest of the code less.
    int holder[26] = {};

    for (char const* p = bytes; *p; ++p) {
        if (*p >= 'a' && *p <= 'z') // omit this check if you're sure it's true
            ++holder[*p - 'a'];
    }

    // With that out of the way, you can also
    // get rid of some of the 97s here:

    int indexOfMax = 0;
    for (int i = 1; i < 26; i++) {
        if (holder[i] > holder[indexOfMax])
            indexOfMax = i;
    }
    return 'a' + indexOfMax;
}

As has been said, you should probably pull the last loop into a different function; I'd say you should pull the array into another function, too. You could use the standard library if you're using C++, but this is also a perfectly fine piece of C code.

Something that you haven't shown us are the tests you're running on this code. Assuming you've factored some things out, so that your function looks like this:

char mostFrequent(char const* bytes) {
    int holder[26] = {};

    populateFromString(holder, 26, bytes);

    return 'a' + findIndexOfMaxIn(holder, 26);
}

Now you can easily test each of the functions separately. For example,

void testPopulationWithAlphabet() {
    char holder[26] = {};
    populateFromString(holder, 26, "abcdefghijklmnopqrstuvwxyz");
    for (int i = 0; i < 26; ++i)
        assert(holder[i] == 1);
}

void testFindIndexOfMaxWithNoDuplicates() {
    int arr[5] = {0, 1, 6, 2, 3};
    assert(findIndexOfMaxIn(arr, 5) == 6);
}

void testFindMostFrequentCharacterWithNoTies() {
    assert(mostFrequent("helloworld") == 'l');
}

You probably want some kind of testing framework to run these tests in, although just using assert.h (or cassert in C++) may also be enough. Your function may be fairly short, but 12 lines is non-trivial, and you'll spend less time debugging if you split your code up and write tests for it.

Answer 3

I agree with @Mike Nakis, plus:

1, The first loop could be changed to

int holder[26] = {0};

How to initialize an array in C

2, The second loop doesn't check that bytes[i] - 97 is lower than 0 or greater than 26 which could cause writes out of the array's memory space.

3, The third loop should be extracted out to a function.

char getMaxIndex(int *input, int length) {
    // TODO: check length, it should be > 0
    int maxIndex = 0;
    int maxValue = 0;
    for (int i = 1; i < 26; i++) {
        if (input[i] > maxValue) {
            maxIndex = i;
            maxValue = input[i];
        }
    }

    return maxIndex;
}

Usage:

return getMaxIndex(holder, 26) + 97;

It improves readability a lot.

Answer 4

I think your solution is optimal in terms of efficiency. One alternative would be to eliminate the last loop which iterates through the holder array to find the maximum by keeping a running max, like this:

int currentMaxChar = 0;
int currentMax = 0;
for (int i = 0; i < length; i++) {
  int c = bytes[i]-97;
  holder[c] += 1;
  if(currentMaxChar == c) {
    currentMax = holder[c];
  }
  else {
    if(currentMax < holder[c]) {
      currentMax = holder[c];
      currentMaxChar = c;
    }
  }
}

But because the last loop has a fixed, extremely small number of iterations, I think your code will probably end up being faster, especially with larger input strings (by using fewer comparisons).