Find first non-repetitive character in a string The original task was to find the first non-repetitive character in a string.

Every now and then I read questions here on Code Review and try answering them myself, and as such I stumbled upon this one.

Now, I have two solutions:

The first one:

struct ch {
    int num;
    char c;
} characters[127];

char find_first_non_repetitive(char *string)
{
    int i = 0;

    for(i = 0; i &lt; strlen(string); i++) {
        characters[string[i]].num++;
        characters[string[i]].c = string[i];
    }

    int index = characters[string[0]].num;
    char c = characters[string[0]].c;

    for(i = 1; i &lt; 127; i++)
    {
        if(characters[i].num != 0 &amp;&amp; first &gt; characters[i].num) 
        {
            first = characters[i].num;
            c = characters[i].c;
        }
    }

    return c;
}


About this one, if using C# instead of C, my idea was to replace struct with an ArrayList&lt;int&gt;.

The second one:

char find_first_non_repetitive(char *string)
{
    const int NUM_CHARACTERS = 127;

    int i = 0, cha[NUM_CHARACTERS];

    for(i = 0; i &lt; NUM_CHARACTERS; i++) cha[i] = 0;

    for(i = 0; i &lt; strlen(string); i++) cha[string[i]]++;

    int index = cha[string[0]];
    char c = string[0];

    for(i = 1; i &lt; strlen(string); i++)
    {
        if(index &gt; cha[string[i]]) 
        {   
            index = cha[string[i]];
            c = string[i];
        }
    }

    return c;
}


Which one is more efficient, and is there an even more efficient way?
Common characteristics

Asymptotic complexity

Both algorithms perform &theta;(n) operations for strings of length n.  Since the task always requires examining every character of the input, there can be no alternative that provides better asymptotic complexity than these do.  Additionally, each has memory overhead that does not vary with the input, which affords no asymptotically better implementation in that respect either.  Of course, implementations with the same asymptotic complexity are not all equivalent by either measure.

See also below, however: your implementations of these algorithms are potentially flawed and less efficient.

Wrong range for char

Your codes assume that the string elements all have numeric value between 1 and 126, inclusive, but char can be a signed type, and whether signed or unsigned it can have more than 7 value bits.  Also, (char) 127 is always a valid char (from C's perspective).  As a result, on any conforming C implementation there are valid C strings which, if provided as input to either of your functions, will cause that function to exhibit undefined behavior.

To solve this problem I suggest declaring your arrays with dimension UCHAR_MAX + 1, and casting input chars to type unsigned char before using them as indexes.

Failure behavior

Each function exhibits somewhat surprising behavior for non-empty inputs that contain no unrepeated characters.  They return that character among those with the minimum number of repeats whose first appearance is earliest in the string.  It's unclear what the function is supposed to do in that case, but the the actual behavior is potentially misleading.  It would be better to return an error code.

You could use 0 as an error code, as it is the only char value that cannot appear inside a string.  Your functions will already return 0 when presented with an empty string as input, though I'm uncertain whether that's by design.  Alternatively, the functions could return type int, with the result being -1 when there is no unrepeated character, else the first non-repeated one cast to unsigned char.  This is the scheme the getchar() function uses.

Loop termination conditions

Both codes contain loops with i &lt; strlen(string) for their termination condition.  The compiler can lift the evaluation of strlen() out of the loop only if it makes several assumptions about that function.  Inasmuch as that's a standard library function, it is conceivable that that would happen, but by no means certain.  If it doesn't happen then your implementations become &theta;(n2) instead of &theta;(n); I therefore recommend lifting the strlen() call out of the loop manually.

Alternatively, consider avoiding strlen() altogether -- since you need to iterate through the whole string anyway, just break the iteration when you reach the terminator.  That should be more efficient.

Using type int for character counters

Each code uses objects of type int as character counters, but


that's a signed type, even though character counts should never be negative, and
its maximum value can be as low as 32767, which is a relatively low limit


I would suggest size_t instead, which should be sufficient for any representable string, but if you prefer something that may be a bit smaller (at the cost of restricting its range) then you could go with uint_least32_t (from stdint.h) for the smallest an unsigned integer type with at least 32 value bits, or uint_fast32_t for the fastest unsigned integer type with at least 32 value bits (these might or might not be the same type).

First implementation

Use of a file-scope variable

This version of the function relies on file-scope variable characters.  Being declared a file scope gets it free initialization, but relying on that makes your function a one-shot.  Even if you reset the contents of this array on each function call, relying on it makes your function non-thread-safe.

I recommend switching to a local (array) variable inside the function.  If (and only if) you continue to use a file-scope variable then at least declare it static to give it internal linkage.

Questionable data structure

The struct ch type on which this version of the function relies seems a bit of a miss to me, for, as it is used, the value of member c is completely determined by the index of a given instance within array characters.  This member is therefore redundant.

See also my previous comments about using type int for your character counters.

Second implementation

Make use of initialization

You declare array cha without an initializer, and then manually loop to set its initial contents.  Given the data type and the initial values you want to set, it would be clearer and potentially more efficient to instead declare it with an initializer:

int cha[NUM_CHARACTERS] = { 0 };


... and skip the initialization loop.  (Elements not explicitly designated in the initializer get initialized to 0.)

Comparative efficiency

It's hard to be sure what to compare here.  The two codes comprise slightly-different versions of the same underlying algorithm.  Implementing fixes for the various shortcomings I discussed would bring them to pretty much the same place, which would look more like the second code than the first.

There are a number of possible variations on this approach, some of which may run slightly faster than others, but I don't see room for anything substantially more efficient.