Homework / toy program - character matching Given a string A = "Hello world" and another string B = "wor", I have to print ("TRUE" or "FALSE") whether the characters in B are present in A. For example, if B = "ollw l" the result should be TRUE; if B = "worlds" the result should be FALSE; if B = "ww", result is FALSE. It has to be done in O(n) time complexity.

My solution is given below. Although this runs in O(n) time I would like some suggestions on how to improve.

int main(void)
{
        char *A = "Hello world";
        char *B = "ollw l";
        int table['z'] = {0};

        while (*A != '\0') {
                table[*A] += 1;
                A++;
        }

        while (*B != '\0') {
                table[*B] -= 1;
                if (table[*B] &lt; 0) {
                        printf("%s\n", "FALSE");
                        return 0;
                }
                B++;
        }
        printf("%s\n", "TRUE");
}
Your algorithm looks alright

The algorithmic idea seems correct and fit for meeting the stated requirements. There are also no unreasonable constant factors or excessive resource usage just to meet the required asymptotic complexity. Overall, I think you did the right thing.

Try to nail down the requirements

I'm not entirely sure what your function is supposed to do. Should it only take into account letters or also other characters like white-space and punctuation? Should it be case-sensitive or insensitive? Either choice is reasonable but one has to be made.

The following item is related to this.

Know your range

You're using an array from 0 (inclusive) to z (exclusive). As others have already pointed out in comments, this means an out of bounds access if the character z occurs in your input which is almost certainly a bug. Adding 1 to the array size might seem to fix the issue but I'd suggest to look more closer at the range of valid inputs.

First, you have to define your range of valid characters. This might be the whole range of the char data type. Which is implementation-defined so you should use the CHAR_MIN and CHAR_MAX macros defined in &lt;limits.h&gt;. (Your input actually can never contain the value 0 because you'd treat it as the sentinel value but wasting that one index seems reasonable.)

If your input range is smaller than that (for example, only ASCII characters or only alphanumeric characters), you should do two things.


Verify that the input is in range and do some reasonable error handling if it is not. If you decide to give your function a narrow contract, invalid inputs mean undefined behavior and you can use the assert macro that is only active in debug builds and gain a little performance in release builds.
Subtract the lowest permissible character from the character at hand to get the index in your array.


For the ASCII character set, the range is [0, 128) and [32, 126) for the printable sub-set. (It would probably be more readable to use ' ' (space) and '~' + 1 in code instead of these magic numbers.)

Be warned that the C standard doesn't require that the character set is ASCII and the ASCII math might be wrong for other encodings. Some encodings also have multi-byte characters and those will cause you never-ending nightmares if you wish to handle them correctly.

Beware of integral promotion

If your input can be the full range of the char data type, there is a nasty culprit here. The C standard doesn't specify whether char is signed or unsigned. If your code is used on an implementation where char is signed, the bytes 0x80 … 0xff will have negative numeric values.

If you compute your indices by subtracting CHAR_MIN, you'll be fine because it will make those values positive again. If you, however, expect values in the range [0, 256) you'll get bad surprises. The usual way to deal with this is to explicitly cast to unsigned char before using the value.

Consider saving some space – or maybe don't

You're currently using an int to count the frequency of a character. This is likely a reasonable choice but I'd like to challenge you to justify it.

If you want to be on the absolute safe side, a size_t will guarantee that you can even deal with the largest possible array, filled with the same character. If you go for size_t, be aware that it is an unsigned type so you cannot check for “less than zero” after the subtraction but have to check for “equal to zero” before subtracting.

If you want to preserve space (and thus get lower cache usage), you might want to reach for a smaller data type but you'll get undefined behavior if its range is exceeded.

Any decision can be justified but you should be aware of its implications. If your function makes assumptions about the maximum frequency of a character, its documentation should state this limitation.

Separate different concerns into different functions

You have put all code into main. This is obviously not a very modular design and hard to unit-test. I'd recommend that you break your logic into at least three functions.


One function that takes two character arrays and checks whether the former contains all characters from the latter. It doesn't print anything but returns a boolean value.
One function that converts a boolean value into a pointer to a statically allocated character array with a human-readable text. This can be as simple as return value ? "true" : "false";.
One function that obtains (or hard-codes) the input, calls the first function to get the result and then prints the human-readable representation obtained from the second function. (You can leave this logic in main if that's all your program does.)